Turing Machines and Finite Automata
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.
|
