|
Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by [Alonzo Church]? in 1936 with the concept of "effective calculability" based on his lambda calculus and by Alan Turing in the same year with his concept of Turing machines. The two approaches are equivalent, an instance of the Church-Turing thesis. |
|
Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by [Alonzo Church]? in 1936 with the concept of "effective calculability" based on his lambda calculus and by Alan Turing in the same year with his concept of Turing machines. The two approaches are equivalent, an instance of the Church-Turing thesis. |
|
The negative answer to the Entscheidungsproblem was then given by Alonzo Church in 1936 and independently shortly thereafter by Alan Turing, also in 1936. 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. |
|
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 function]?s) 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. |
![[Home]](wikipedia.png)