The hypothesis that any function which can be computed at all by an effective, mechanical procedure can be computed by a Turing machine, tying together several independently developed models of computation into a single shared notion of what it means for something to be computable.
Facts
Partially Attested
Origin YearChurch formulated the thesis over 1935 to 1936 and Turing independently produced his own formulation in 1936; 1936 is the year both formulations were in place, so this is an approximate single-year value for a multi-year origin. Core PrincipleA function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. 1 Connections
In Field
Invented
Alan Turing independently formulated the equivalent claim in 1936 using Turing machines, giving the thesis its joint name.
Alonzo Church proposed the equivalence of effective calculability with lambda-definability in 1936.
Sources
1. Church-Turing thesis, Wikipedia
Lead section, second sentence
It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.
History, subsection Circa 1930 to 1952
and then proved (1936) that the Entscheidungsproblem is unsolvable
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.