Computation Beyond Turing Machines
1 Gödel proved that logic could not completely model mathematical truth. Computer science is a fundamentally non-mathematical discipline. Interaction is not the only way to extend Turing machine. 1900—Hilbert's principle, 1931—Gödel proved that Entscheidungsproblem is unsolvable. 1935—Church proved thath Entscheidungsproblem could 2 not be solved by the lambda calculus. Turing: halting problem of Turing machines. → Church-Turing thesis: logic, lambda calculus, Turing machines, and effective function computations are equals as problem solving mechanisms.
Algorithm: predetermined input → output. Interaction cannot be replaced by any set of inputs determined prior to the computations: AI, graphics, and the Internet could not be expressed by TM.
3 the classical Turing paradigm may no longer be fully appropriate to capture all features of present-day computing
Sergey Vartanov, 2007–2020