Turing is the father of computer science, laying the theoretical foundation for the creation of computers, and his related Turing machine can be said to be the Nobel Prize in the field of computer.
What Turing did was clearly define computation, define the universal machine, and prove the equivalence between computational models, as well as the limits of computational models.
Contributions
Turing has made outstanding contributions to the field of computers and cryptography, with the following major achievements:-
Computability theory
Turing defined computable functions from a completely new perspective. He comprehensively analyzed the human computational process and reduced computation to the simplest, most basic, and most definite operational actions, thus describing the basic computational procedures that are intuitively mechanical in nature in a simple way, so that any mechanical (capable) procedure can be reduced to these actions. This simple approach is based on a notion of abstract automata, with the result that an algorithm computable function is a function that such an automaton can compute. This not only gave a completely definite definition of computation, but also for the first time linked computation and automata, which had a great impact on later generations, and this "automaton" was later called "Turing machine".
-
Determination of the problem
Turing used his method to solve the famous Hilbert's decision problem: the decision problem of satisfiability of formulas for narrow predicate arithmetic (also called first-order logic). He encoded Turing machines with formulas from first-order logic, and then derived the undecidability of first-order logic from the undecidability of the Turing machine stopping problem. The "encoding method" he coined here became one of the main methods for proving the undecidability of the formula class of first-order logic.
-
Artificial Intelligence
Turing proposed the famous "Turing Test", which states that if a third party cannot tell the difference between human and artificial intelligence machine responses, it can be concluded that the machine has artificial intelligence.