COMPUTATIONAL ADEQUACY THEOREM
\kˌɒmpjuːtˈe͡ɪʃənə͡l ˈadɪkwəsi θˈi͡əɹəm], \kˌɒmpjuːtˈeɪʃənəl ˈadɪkwəsi θˈiəɹəm], \k_ˌɒ_m_p_j_uː_t_ˈeɪ_ʃ_ə_n_əl ˈa_d_ɪ_k_w_ə_s_i θ_ˈiə_ɹ_ə_m]\
Sort: Oldest first
-
This states that for any program (a non-function typed term inthe typed lambda-calculus with constants) normal orderreduction (outermost first) fails to terminate if and only ifthe standard semantics of the term is bottom. Moreover,if the reduction of program e1 terminates with some headnormal form e2 then the standard semantics of e1 and e2 willbe equal. This theorem is significant because it relates theoperational notion of a reduction sequence and thedenotational semantics of the input and output of areduction sequence.
By Denis Howe
