Alan Turing proposed a Turing machine (see its exact definition there) as a universal computing device.

So how can we view any kind of computation as being expressible by means of a Turing machine?

In using Turing machines to express particular algorithms, we need a convention to present it with input. The input must somehow be present on the initial tape content and the Turing machine must 'recognise' it. The usual custom is to assume a specific "blank" symbol and to only consider the action of Turing machines on initial tape contents that are all blank except on a certain finite sequence of positions, starting under the tape head and extending to the right, never containing more than two blanks in a row. Let's call such a state of the tape 'clean'. A clean tape effectively represents a sequence of data items. For instance, if the nonblank symbols are interpreted as digits, it represents a sequence of natural numbers.

Similarly, we need a convention to describe how a Turing machine produces a result. Every halting computation of a Turing machine leaves the tape in a certain state. The usual custom is to consider only Turing machines that whenever they halt, do so leaving a 'clean' tape. Every Turing machine can be modified to do this, by adding a special 'cleanup routine' part and appriopriate transitions invoked whenever the original machine would halt.

With these conventions, Turing machines express functions on natural numbers. For example, a TM implementing multiplication in this manner would, when started on a clean tape encoding a sequence of two numbers, always halt leaving a clean tape encoding the product of these two numbers. Predicates can be expressed as functions that always produce 0 or 1.

It is in fact possible to write a Turing machine that expresses multiplication in this way. What is more, every algorithm, every computational process, can be expressed in this way - this is known as Church's Thesis. Note that this is not a mathematical proposition, but rather, a definition of what we humans mean by the words algorithm and computation. Things like event handling (timers, the arrival of input) and synchronization aren't part of this notion of algorithm; other mathematical models exist to express such things.

Log in or register to write something here or to contact authors.