Beyond Turing Machines

Turing [8] introduced the concept of "computing machines" which subsequently were called Turing machines. He proved that Hilbert's decision problem(Entscheidungsproblem) is unsolvable, that is, there is no Turing machine determining whether or not a given statement in first-order predicate calculus (a mathematical proposition in number theory) can be proved. Wegner [11] writes that Turing's precise characterization of what can be computed established the respectability of computer science as a discipline. He argues that Turing machines cannot capture the intuitive notion of what computers compute when computing is extended to include interaction. His interaction machines have been criticized as an unnecessary Kuhnian paradigm shift [12]. Prasse and Rittgen [7] write that Wegner's "interaction machines cannot compute non-recursive functions, so Church's thesis still holds". This implies that interaction machines cannot "compute" functions not computable by Turing machines. This work is licensed under the Creative Commons Attribution-No Derivative Works 3.0 Unported License (see http://creativecommons.org/licenses/by-nd/3.0/).