25,161
edits
Changes
m
Heiner Marxen's Busy Beaver link
<span id="TuringMachine"></span>
=Turing Machine=
[https://en.wikipedia.org/wiki/Turing_machine Turing machines] are abstract symbol-manipulating devices which can be adapted to simulate the logic of any computer algorithm, described in 1936 by Alan Turing <ref>[[Alan Turing]] ('''1936'''). ''On computable numbers, with an application to the Entscheidungsproblem''.</ref> , as thought experiment about the limits of mechanical computation. An example of a concrete Turing machine is the [https://en.wikipedia.org/wiki/Busy_beaver Busy beaver] <ref>[https://web.archive.org/web/20031205193625/http://www.drb.inselturbotm.de/~heiner/BB/index.html Busy Beaver] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine]) by [[Heiner Marxen]]</ref>.
The [https://en.wikipedia.org/wiki/Universal_Turing_machine Universal Turing machine] can simulate an arbitrary Turing machine on arbitrary input, and can be considered as the origin of the [[John von Neumann]] [https://en.wikipedia.org/wiki/Von_Neumann_architecture architecture]. A universal Turing machine can calculate any [[Recursion|recursive]] function, decide any [https://en.wikipedia.org/wiki/Recursive_language recursive language], and accept any [https://en.wikipedia.org/wiki/Recursively_enumerable_language recursively enumerable language]. According to the [https://en.wikipedia.org/wiki/Church-Turing_thesis Church-Turing thesis], the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms. For these reasons a system that can simulate a universal Turing machine is called [https://en.wikipedia.org/wiki/Turing_completeness Turing complete].
