Turing machine

From Esolang
Jump to navigation Jump to search
Not to be confused with Turing-machine.

A Turing machine is an imaginary machine devised by Alan Turing which performs computations. It consists of a finite-state automaton (often called its "control mechanism" or program) hooked up to an unbounded tape which can be moved to the left and right, from which symbols can be read, and onto which symbols can be written.

A universal Turing machine is a Turing machine which can be given a description of any arbitrary Turing machine encoded in some form, initialized on its tape, and the finite state machine operates on the description in such a way that the described machine is simulated. Universal machines are named for the fact that they can compute any computable sequence.

Turing machines are computationally significant because, while many systems of computation have been shown to be able to solve only a subset of computation problems that a given Turing machine can solve, no system of computation has ever been shown to be able to solve a computation problem that a Turing machine cannot.

In addition, no well-defined algorithm has yet been devised that a universal Turing machine is demonstrably incapable of executing. This has led to the Church-Turing thesis, which states (roughly) that Turing machines are mechanical embodiments of (what we think of intuitively as) effectively computable algorithms. That is to say, a Turing machine can make any sort of calculation that it is possible to precisely define an algorithm for.

Since the invention of Turing machines in Alan Turing's paper, many other systems have been shown to be equivalent to them. (In fact, several of these systems, such as the lambda calculus, combinatory logic, and Post canonical systems, predate the Turing machine.) In this way, Turing machines define a computational class of equivalent systems; these systems are termed Turing-complete.

For all these reasons, it is often an interesting and/or valuable task to show that an esoteric programming language is (or is not) equivalent to a Turing machine.

External resources