Alan Turing is one of the pioneers of the computability theory and logic formalization. He came up with the hypothesis of which algorithms can be implemented and computed by machines (Turing's thesis), created an abstract model of such machine (Turing machine), and described absolutely vital abilities of any system for being able to realize any logic that can be computed(Turing completeness).
Turing's thesis is only one of the existing formal systems in the computability theory. There are also λ-calculus, Markov algorithms, but they all were implemented on the Turing Machine that is used at this time as a general computational model to classify which real-world systems (mostly programming languages) are able to compute mathematical functions or implement algorithms.
All existing computability theories are defined on discrete values, and the domain is the set of Natural numbers.
I prepared several mindmaps to summarize basic ideas and statements:
Turing's thesis :
Turing machine :
Turing completeness :
Top comments (0)