In the 1930s, Alan Turing was researching the possibilities of Turing machines. Meanwhile, in the United States, Alonzo Church was delving into the semantics of a formal system called lambda calculus that he had created.

The two issues appear to have little in common at first glance. However, when the two men came across one other's work, they immediately realized something unexpected and crucial. Everything recursive turns out to be Turing-computable, and vice versa.

This conception leads to the Church-Turing thesis, which states that a Turing computer must also compute any process.

Notion of computability

Several distinct attempts to codify the concept of computability in the 1930s:

• In 1933, Kurt Godel and Jacques Herbrand formalized the definition of the class of general recursive functions: the smallest class of functions (with an arbitrary number of arguments) that is closed under composition, recursion, and minimization, and that includes zero, successor, and all projections.
• In 1936, Alonzo Church devised the -calculus, a mechanism for defining functions. Within -calculus, he described the Church numerals as an encoding of the natural numbers. 
• Alan Turing constructed a theoretical model for machines, now known as Turing machines, that could do calculations from inputs by manipulating symbols on a tape in 1936, before learning about the church's work. 

Myth around Church–Turing thesis

The above three technically defined classes of computable functions overlap, according to Church, Kleene, and Turing: 

• a function is recursive if and only if it is Turing computable, and 
• if and only if it is general recursive.

This approach has prompted mathematicians and computer scientists to assume that these three similar processes adequately capture the concept of computability. 

The Church–Turing thesis, on the other hand, claims the informal notion of an effectively calculable function. However, although the idea is widely accepted, researchers cannot prove it formally since the concept of effectively calculable is instead loosely defined.

Chronicle of Church–Turing thesis

The Entscheidungsproblem of David Hilbert and Wilhelm Ackermann, which inquired whether there was a mechanical technique for separating mathematical truths from mathematical falsehoods, was one of the most critical problems for logicians in the 1930s. This quest necessitated the definition of "algorithm" or "effective calculability," at least sufficiently for the search to begin. But, right from the start, Alonzo Church's efforts sparked a dispute that continues to this day.

It was the idea of "effective calculability" to be 

(i) an "axiom or axioms" in an axiomatic system, 

(ii) only a definition that "identified" two or more propositions, 

(iii) an empirical hypothesis by natural events, or 

(iv) just a proposal for the sake of argument (i.e. a "thesis").

Conclusion

One of the most common is that a Turing machine can do any calculation that works. But unfortunately, the Church-Turing thesis is often misunderstood, especially in recent works on the philosophy of mind.

Church only thought about functions of positive integers. Turing planned to write another paper about the theory of computable functions of a real variable, but he never did.

A more significant difference was that Turing's approach was essential for the new science of automatic computation. Church's approach didn't talk about computers, but Turing's did. In his 1937 review of Turing's paper, the church called Turing's approach the "Turing machine." The "Turing machine" is an abstract computer that encapsulates the fundamental logical principles of the stored-program all-purpose digital computer.