Turing machine

From Esolang
(Redirected from UTM)
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 definable as a set of algorithms 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.

Formally, Turing machines are often described in a tuple format, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (\Sigma, \sigma_0, Q, q_1, q_h, f)} , consisting of:

  • A set of symbols Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma}
  • A blank symbol Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma_0}
  • A set of states Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q}
  • A starting state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_1}
  • A halting state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_h}
  • A transition function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f: Q \times \Sigma \rarr \Sigma \times D \times Q}
    • Where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D} is generally either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lbrace left, \ center, \ right \rbrace} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lbrace left, \ right \rbrace}
    • Undefined for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_h}
    • Taking in the current state and currently observed symbol, then producing a new symbol to overwrite the observed, a direction to move in, and the next state to transition to

A Turing machine described this way can be thought of a partial function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Phi: \Sigma^{\ast} \rightharpoonup \Sigma^{\ast}} taking in a preset tape of symbols of some finite length, and producing (through the mutative operation of the machine) a new finite string of symbols on the tape. Since the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma^{\ast}} is countably infinite, the partial function of a Turing machine can also be written as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f: \mathbb{N} \rightharpoonup \mathbb{N}} for some encoding scheme between the naturals and symbol strings. The function is partial since the machine may loop indefinitely instead of producing an answer. The notation for a Turing machine Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} which halts on an input tape Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M(x)\darr} , and one which does not halt on that input is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M(x)\uarr} .

Variants

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Turing_machine&oldid=154622"