A Turing Machine is a simple mathematical model of computation that is powerful enough to describe any computation a computer can do.

Imagine a robot, in front of a little whiteboard, with infinitely many whiteboards to both sides, finitely many of which have a symbol written on them. The robot can erase the contents of a whiteboard and replace it with some other symbol, and it can move over to the next whiteboard on the left or right, or shut down. This is all the robot can do. The robot's actions are determined by only two things: the symbol on the whiteboard it just saw, and its internal state. The output of this process is defined to be "whatever is written on the string of whiteboards when the robot has shut down".

This is equivalent to a Turing Machine (with the robot replaced by a machine head and the infinite line of whiteboards replaced by an infinite tape subdivided into cells). The halting problem (which is unsolvable in general) asks whether the robot will eventually shut down at some point.

So, a Turing Machine can be specified with the following information:

A finite set of symbols the robot can write (one of which is the null symbol, an empty board).

A finite set of states the robot can be in (at least one of which causes the robot to shut down).

A starting state for the robot.

Starting symbols on finitely many of the boards (whiteboard location and symbol type data).

A transition function for the robot, which takes a symbol/state pair as input, and has a triple as output. For example, ine such transition might be represented as if symbol is 7 and state is FQUF, then (erase and write 4, set state to ZEXA, move left).

Surprisingly enough, other proposed models of computation have all been shown to be weaker than, or equivalent to, Turing Machines! With infinite memory space, and sufficiently intricate sets of symbols and states, the robot and whiteboard (or machine head and memory tape) system can compute anything at all that is computable in principle! This fact is known as the Church-Turing thesis; it's very widely believed to be true, and certainly no-one has ever found any hint of a counterexample, but it's not "proved" in any meaningful sense.

Variants of Turing machines

Multi-tape Turing Machines would be equivalent to having several robots in infinite whiteboard hallways, except that the robots are networked together to all share the same state. An example state transition is as follows:

If symbol A is * and symbol B is 6 and symbol C is absent and state is VREJ, set state to IXXI, robot A writes ! and moves left, robot B writes 9 and moves left, robot C writes = and doesn't move.

These Multi-tape Machines can speed up some computations polynomially (so, for example, a problem which would normally take 1 million steps to solve may be solvable in a thousand steps, because of the square root speedup). Because these machines can only muster a polynomial speedup, and moving to a one-tape Turing Machine only incurs a polynomial slowdown, the computational complexity class P is unchanged across Turing Machines with different numbers of tapes.

Write-only Turing Machines are Multi-tape Turing Machines where one of the tapes/hallways of whiteboards has its input ignored when determining the next state, written symbols and movements. We can think of this situation as one where one particular robot is blind.

Read-only Turing Machines are Multi-tape Turing Machines, and one of the tapes/hallways of whiteboards cannot be rewritten. The robot in there can only move around and observe, but it has not been given a pen or rubber so it can't write on or erase the boards.

Oracle Machines (which are more powerful than Turing Machines, and don't exist in reality, though they are a very useful tool in computational complexity theory), are like a mult-tape machine with exactly two tapes: one tape is designated as the "oracle tape", and one tape as the "machine tape". This time, one of the robot states is "INVOKING MAGIC ORACLE". When that happens, the contents of the whiteboards in the machine hall (that is, the contents of the machine tape) are interpreted as the description of a problem, and then a correct solution to the problem magically appears on the string of whiteboards in the oracle hall (that is, on the oracle tape), completely erasing whatever was on the oracle hall whiteboards originally; and finally the oracle robot is moved to the first whiteboard of the answer.

Therefore the functionality of the oracle machine depends very strongly on what the oracle does! A given oracle machine might do one thing when the oracle does "compute the factorial of the number I was called with" than when it does "compute whether or not the number I was given is the description_number of a halting Turing machine".

Oracle machines are like ordinary Turing machines, except we also give them the ability (in principle) to obtain instant correct answers to any particular problem. The problem we may instantly solve is fixed in advance, before we ever start running the machine. With the right oracle, oracle machines can solve any problem, where Turing machines cannot (recalling that the halting problem can't be solved by Turing machines). However, the price is that oracle machines don't exist: they require a magic oracle, and we don't have any of those in nature.

Posts

Wikitag Contributions

Comments