This article marks out the boundaries between Turing Machines, Universal Turing Machines, and finite automata.
Turing Machines and Finite Automata: The Basic Distinctions
The capabilities of Turing Machines, Universal Turing Machines, and finite automata are easily confused, and usage outside the specialist literature doesn’t help.
Of the three, Universal Turing Machines are the most powerful. The Universal Turing Machine was originally described independently but equivalently by Alan Turing and Emil Post (see Davis 1965 or van Heijenoort 1967 for the original papers). It is a general purpose digital computer which can simulate any other digital computer. Formally, this means that for any other computer M, a program p for M can be prefixed with a fixed length segment of code s for Universal Turing Machine U such that sp causes U to perform the same computation as p for M. The fixed length segment s just tells U how to simulate the behaviour of M. This is much like the piece of software which enables a Macintosh personal computer to emulate computers based on an entirely different Intel chip set and thus to run their software unmodified. It is widely — and incorrectly — held that a Universal Turing Machine can simulate any physical process at all.
The name ‘Turing Machine‘ is often used to include all kinds of Turing Machines (Universal, uniform, non-uniform, oracle machines, etc.), but used narrowly it simply picks out the class of ordinary Turing Machines which lack the universal computational abilities described above.
Finally, the class of finite automata is set apart by the fact that they may exist in only a finite number of distinct states. Unlike the Universal Turing Machine, which may write any of an infinite set of binary strings on its infinitely long tape, finite automata can display only a strictly finite number of distinct states. Whereas the Universal Turing Machine can, for intance, enumerate infinitely many natural numbers by virtue of its unlimited tape capacity, any finite automaton for enumerating natural numbers will always be limited by some largest number beyond which it cannot continue.
Relations Between Computation Models
Their finiteness guarantees that for any finite automaton, there exists some Turing Machine which can calculate the same function (i.e., which can simulate it). Likewise, the definition of Universal Turing Machine guarantees that for any Turing Machine, any Universal Turing Machine can simulate it. Similarly, any Universal Turing Machine can simulate any finite automaton. Some Universal Turing Machines running particular programs compute functions equivalent to those computed by less powerful (non-universal) Turing Machines or even finite automata, but no program can give a non-universal Turing Machine universal power, and no finite automaton has universal power.
Observations About Finite Automata and Chaos
A few features of finite automata are worth keeping in mind when it comes to claims sometimes made about chaos:
- The state space of a finite automaton consists wholly of fixed points and orbits.
- Strange attractors do not exist in the state space of finite automata.
- Finite automata cannot display sensitive dependence.
- Finite automata cannot display chaotic behaviour, as formally defined.
- Research Archive
- About the Research Archive
- Drafts and Unfinished Papers
- International Workshop on Robot Cognition
- Mind Out of Matter
- Research Bibliography
- Supplementary Bibliography from Mind Out of Matter
- Tutorials and Introductions
- Biological Cognition & Universal Computation
- Chaos Theory
- Complexity & Information Theory
- Computability and Completeness
- Emergence and Levels of Description
- Models of Computation: Turing Machines and Finite Automata
- Philosophers’ Zombies and their Role in Cognitive Science
- Quantum Decoherence
- Recursion Theory
- Soul Searching (TV Documentary)
This article was originally published by Dr Greg Mulhauser on .on and was last reviewed or updated by