Turing machine

A Turing machine is an important computer model of theoretical computer science. A Turing machine models the operation of a computer in a particularly simple and mathematically well to be analyzed manner. It is named after the mathematician Alan Turing, who introduced it in 1936.

Turing machines make the terms of the algorithm and the predictability mathematically comprehensible, that is, they formalize these concepts. In contrast to a real computer, a Turing Machine is a mathematical object and thus can be examined using mathematical methods.

A Turing machine represents an algorithm or program. A computation consists of gradual manipulation of symbols or characters according to certain rules written to a storage tape and read from there. Chains of these symbols can be interpreted in various ways, including as numbers. This describes a Turing machine is a function which strings that are initially on the tape, on strings that come after " processing " through the machine on the strip maps. A function that can be calculated using a Turing machine is a Turing -computable or simply called predictable.

• 8.1 Hardworking beaver
• 8.2 ant

• 9.1 oracle Turing machine
• 9.2 Probabilistic Turing machine
• 9.3 quantum Turing machine
• 9.4 Persistent Turing machine

Informal Description

The Turing machine has a control unit in which the program is located and also consists of

• An infinitely long memory tape with an infinite number of sequentially arranged fields. Per field can be stored exactly one character. In addition to the input alphabet is as an additional sign a blank icon " empty field " approved which does not belong to the set of input strings.
• A programmatic read and write head that can move on the storage tape by field and change the sign.

The Turing machine modifies the input on the tape after the specified program. The starting position of the Turing machine is at the beginning of the input word, i.e., at the position of the first input character.

With each step reads the read-write head of the current character, this will overwrite with another (or the same ) characters and then moves one space to the left or right or stops. What sign is written and what movement is executed depends on the encountered at the current position mark and the state in which the Turing machine is currently located. This is defined by one belonging to the Turing machine function. At the beginning, the Turing machine in a predefined initial state and goes with every step into a new state. The number of states in which the Turing machine can be located, is finite. A state can be run through several times, he says nothing about the characters present on the tape from.

One can define certain states of the Turing machine as final states. Once the machine is in one of these states, it will stop, regardless of which character is located at the current position. There are inputs for which a Turing machine never stops.

The Turing machine is - like many other machines also - used for decision problems, so for questions that are or "no" answer with "yes". Certain conditions are known as " accepting ," "not accepting " defined as other. The input is exactly accepted if the Turing machine ends in an accepting final state.

Importance

The mathematician Alan Turing introduced the Turing machine in 1936 specifically to address the so-called decision problem in Scripture On Computable Numbers, with an Application to the decision problem, in the context of the formulated by David Hilbert in 1920 Hilbert program.

, Drawn up by Hilbert decision problem asks whether a formula of predicate logic is universal, so if any interpretation of a mathematical, ie formal logical statement is true. Its proposed Hilbert program tried to solve this problem automatically. The method that determines for a predicate logic formula, whether it is universal, so should be able to be carried out by a "machine". Before the invention of the computer, this meant that a person according to fixed rules - an algorithm - performs a calculation.

Turing defined his model with the concepts of algorithm and predictability as a formal, mathematical terms. In general, it is assumed that the Turing -computability the intuitive understanding of predictability is true, this statement is known as the Church - Turing thesis. You live a strong plausibility held, inter alia, by the mathematical equivalence of the notion of Turing computability with computability other terms ( such as the expressibility in the lambda calculus, or as a partially recursive function, as well as the predictability by register machines, which are modeled on computers used structurally today). The special feature of a Turing machine is its structural simplicity. It only needs three operations (read, write, and read-write head to move ) to simulate all the operations of the usual computer programs. As part of the theoretical computer science therefore it is particularly well suited to the proof of properties of formal problems as they are considered by the complexity and computability theory.

The complexity (such as running time and space complexity ) of algorithms are defined in terms of certain machine models. Turing on machines such as the asymptotic number of state transitions in response to the input length of a possible Laufzeitkomplexitätsmaß an algorithm. On other models complexity measures are often defined, defining a random access to each memory cell or performing arithmetic operations as separate steps. These dimensions are within the limited framework ( small amounts of data or smaller numbers ) are particularly suitable to estimate the duration of many algorithms on real computers and are therefore often (especially unspecified) encountered. Due to the sequential structure of Turing machines, therefore the runtime complexity in terms of the asymptotic number of state transitions for many algorithms is compared with definitions for register machines higher. Complexity theory deals with the question of which problems algorithms with complexity which exist, for example in which complexity classes problems lie or not lie. Unless it when examining the runtime complexity is not polynomial in the input length arrives on factors that Turing machines are here quite generally applicable, since the simulation of many Register Machines means only polynomial overhead in many complexity measures.

Not all mathematical functions can be computed by a Turing machine, even if you limit yourself to well-defined functions with finite input and output (such as can be functions between arbitrary real numbers do not represent by functions with finite input and output, since the real numbers are uncountable are, and there are formally seen functions that can not be specified). So Turing was able to show that a Turing machine, the decision problem can not be solved, just like the halting problem.

Also undecidable is by the theorem of Rice any non- trivial property of a program in a Turing powerful language. Even if we restrict ourselves to terminating Turing machines, it is undecidable whether two terminating Turing machines accept the same language. The computability theory is concerned with the question of which problems are from which machine models predictable or not predictable.

Systems, computers and programming languages ​​that could emulate a Turing Machine by disregarding the limitations of memory and related properties are called Turing complete.

Formal definition

Formally, a deterministic Turing machine can be represented as a 7- tuple ( see also non-deterministic Turing machine).

• Is the finite set of states
• Is the finite input alphabet
• Is the finite tape alphabet, and it is
• Is the (partial ) transition function
• Is the initial state
• Stands for the empty field ( Blank )
• Is the accepting state

Configurations

The configuration of a Turing machine not only describes her own current state, but also the position of the read - write head and the existing just on the tape symbols.

The icons are in a finite portion of the tape, which is surrounded by an infinite number of empty symbols. It is therefore sufficient to consider this area.

Formally, a configuration of a Turing machine can be described by a sequence.

Is the left-most non- empty band and the symbol at the rightmost not - empty band symbol. Moves beyond the read-write head over the edge of the configuration are still add other icons.

The read - write head is located above the sign, its position can thus also note with short. This position is characterized in that, the state of the Turing machine is in the configuration before the symbol.

With a launch configuration, the input word is set. A common initial configuration is with starting state and input word.

Calculation

The transfer function is added to a startup configuration before the expiry of a Turing machine. She changes in one step from the current configuration to the successor configuration. Such a move from configuration to configuration can be as shown.

Writes the transfer function for a state and the input symbol as before, that is written, the read-write head moves to the left and the successor state, this means the following step.

The computation of a Turing machine is a finite or infinite sequence of configuration steps. A Turing machine accepts a given by the boot configuration word when the calculation begins in this initial configuration and ends in a configuration in which is the Turing machine is in state. Ends the calculation in a different configuration, the Turing machine rejects the input word. If the computation of the Turing machine infinite, the word is neither accepted nor rejected.

Intuition

The Turing machine performs a calculation by transforming gradually an input to an output. Input, output and intermediate results are stored on the infinitely long tape.

At the beginning there is a word as input on the tape ( per tape field is a string of the input word ), the rest of the band consists of empty fields. The read-write head is on the first character of the input and the Turing machine is in start state.

The transition function specifies how the Turing machine step by step reads the tape contents and describes changes its state and changes the position of the read -write head. This function takes as an argument the current state and the character that is in the current configuration under the read -write head. As a result, it then delivers exactly one state ( this is the successor state of the Turing machine ), a character ( this is the contents of the field to which, the read-write head, overwritten ) and either the symbol L (in this case moves the read-write head one square to the left), R ( in this case, it moves one space to the right) or 0 (then it remains on the same box ). Thus the Turing machine has undergone a step of their work cycle and is ready for another.

Since the transfer function is partial, it does not have to define a transition for each state and each input character. The final state has a successor state, for example, no input character. Reaches the final state of the Turing machine, the Turing machine can therefore perform no further actions, and the calculation is finished. The output is then the contents of the tape (the fields that are filled with symbols from particular symbol are not considered).

Depending on the tape alphabet Ein-/Ausgaben and caching can be made differently marked.

Example

The following deterministic input Turing machine expects a sequence of ones as the input to the tape. It doubles the number of ones, with a blank icon remains in the middle. From "111", for example, the string " 1110111 ". The write head is located initially on the first one. The initial state is the final state. The zero stands for the empty box and the tape is filled to the ones written on them with empty fields.

The transfer function is defined as follows:

Passes, for example, when entering "11" following states, the current head position is in bold:

The calculation starts in the initial state. Here, the first one is replaced by an empty field, the read-write head moves to the right and new state. The head now migrates as long as the right until a blank field is read. Then the Turing machine enters the state and reads all the other ones, until it finds an empty box again. This is then replaced by a one. In the state, the head moves back over again reads all ones, until it encounters an empty field, change of state on. The head moves now long left until the originally written in state empty field is found. This is again replaced by a one, the head of a field moves to the right and the Turing machine comes back to the state. Here begins a new computation cycle. A blank field in the read state, the Turing machine enters the final state, whereupon the calculation is ended.

Equivalent variants of the Turing machine

In the literature, there are many different definitions and variants of the Turing machine, which each differ in some details. Is varied as the tape used alphabet, special signs used in addition, the definition of acceptability and other properties. There are also extensions with more tapes or additional stacks, which are also in terms of computation equivalent to Turing machines. Self- complexity theory, the differences between many of the variants are largely negligible. Thus, about one in f (n) - ​​time bounded k- tape machine to any large k can be simulated by an O ( f ² ( n ) ) time-limited 1- tape machine. So for the simulation of any number of bands, there is a maximum square overhead. Total number of variations lead to no more than polynomial effort differences (where effort here any resource says ) and are therefore for many complexity-theoretic investigations negligible. It adjusts depending on the goals of the analysis, the model used so that the analysis can be as simple as possible carried out. There are, however, in terms of predictability, but not the complexity (in the sense of " up to polynomial overhead " ) equivalent extensions of the Turing machine, such as certain oracle Turing machines.

Forgetful Turing machine

A Turing machine is oblivious (or uniform motion ) mentioned if the head movements do not depend on the contents of the input, but only on the length. Each Turing machine can be simulated by a forgetful.

Universal Turing machine

In the above definition, the program is built into the machine and can not be changed. Keyed to the description of a Turing machine as sufficiently simple string, it can be called a universal Turing machine - even a Turing machine - construct, which takes such an encoding of an arbitrary Turing machine as part of its input and simulates the behavior of the encoded Turing machine on the also given input. For example, from the existence of such a universal Turing machine follows the undecidability of the halting problem. A similar idea, in which the program is considered a part of the variable input data is also almost all of today's computer architectures based ( Von Neumann architecture).

Formally, a universal Turing machine is a machine that reads an input. The word here is a reasonably simple description of a machine that computes a particular function with input the output. is a delimiter between program description and input. thus simulates the behavior of using the functional description and the input. The index indicates that there is no single universal Turing machine. So could understand, for example, and different words. The word has to be coded in a language understood by the.

Known Turing machines

Hardworking beaver

As Busy Beavers ( engl. Busy Beaver ) deterministic Turing machines are expressed relative to all terminating, deterministic Turing machines with the same number of states and symbols to write the maximum number of a particular symbol on the tape and then stop. There is no computable function that a given number of symbols and states a corresponding industrious beaver, the number of characters written by him at the end symbols ( the so-called Radó function) or the number of steps that it needs to schedule around that maps.

Ant

Chris Langton's ant is a Turing machine with two dimensional tape and very simple rules, the tape contents first ( as a two-dimensional image ) looks chaotic, but out forms a certain structure visible by over 10,000 steps.

On Turing machine ajar machine models

Oracle Turing machine

Oracle Turing machines are generalizations of the Turing machine in which the Turing machine can perform some additional operations in one step, as solutions of undecidable or only with great effort decidable problems. Thus allow oracle Turing machines, a further categorization of undecidable problems, see Turing degree, or even the definition of additional complexity classes.

Probabilistic Turing machine

Probabilistic Turing machines allow for each state and each input two (or equivalently, finitely many ) possible transitions, one of which in the execution - expressed intuitive - one is selected at random, and are used for theoretical description of randomized algorithms.

Quantum Turing machine

Quantum Turing machines are used in quantum computer science as an abstract machine models for the theoretical description of the possibilities of quantum computers. Quantum circuits are to be mentioned in this context as another popular model.

Persistent Turing machine

To interactive models to be represented by a Turing machine (in the sense of " models with memory" ), is an extension of the same necessary to give this memory.

According to the definition ( Goldin et al, 2003. Turing Machines, Transition Systems and Interaction ) is a persistent Turing machine (PTM ) is a nondeterministic 3- tape Turing machine with an input, a labor and an output tape. The input is processed on the working tape and only after processing is complete, enter the results on the output tape back in the "Environment". Then you can re-enter from the environment are processed. Between two steps, the contents of the work tape remain as "memory".

Relationship between a Turing machine and a formal language

Accepted language

A Turing machine accepts a language when it merges with the input of each word after finitely many steps to a defined final state ( "holds" ) and input of each word in a different state or is not holding.

A language is said to be recursively enumerable or semientscheidbar (type 0, the Chomsky hierarchy ), if there is a Turing machine that accepts.

Decidable language

Accepts a Turing machine is a language and keeps them in addition to all entries that do not belong to this language, as decided by the Turing machine that language.

A language is recursive or decidable if and only if there exists a Turing machine that decides L.