"The negative answer to the Entscheidungsproblem was then given by Alonzo Church in 1936 and independently shortly thereafter by Alan Turing, also in 1936. Church proved that there is no algorithm (defined via recursive functions) which decides for two given lambda calculus expressions whether they are equivalent or not. He relied heavily on earlier work by Kleene. Turing reduced the problem to the halting problem for Turing machines and his paper is generally considered to be much more influential than Church's. The work of both authors was heavily influenced by Kurt GĂ¶del's earlier work on his incompleteness theorem, especially by the method of assigning numbers to logical formulas in order to reduce logic to arithmetic." from Wikipedia |