4 ms·
A (Universal) Turing Machine is a computation machine that can simulate (virtualize) the operations of any other computation machine, including itself, given en
by iwr 16y ago
A (Universal) Turing Machine is a computation machine that can simulate (virtualize) the operations of any other computation machine, including itself, given enough memory and time.
A Turing-complete language is capable of functionally expressing a Turing machine. That is, given the theoretical construct, can the language encode it? An equivalent framework is lambda calculus. Any Turing machine can be expressed as lambda-expressions and vice-versa.
The physical world analog to the Turing machine is the Universal Constructor, a machine that can construct a duplicate of itself or a functional analog of any other machine that can duplicate itself, given enough time and raw materials.
These concepts are relevant because it's not clear if there is a class of problems not solvable by Turing machines (but solvable by another class of machines). As far as we know, human beings themselves are Turing machines (and constructors) and nothing more.
- Locke1689 16y agoPlease note that there is no system in existence which is a Universal Turing machine. All possible physical systems are finite state machines.