Turing machine

A Turing machine is an important computer model in theoretical computer science . A Turing machine models the functioning of a computer in a particularly simple and mathematically easy to analyze way. It is named after the mathematician Alan Turing , who introduced it in 1936.

Turing machines make the concepts of algorithm and computability mathematically comprehensible, that is, they formalize these concepts. In contrast to a physical computer, a Turing machine is a mathematical object and can be examined using mathematical methods.

A Turing machine represents an algorithm or a program. A calculation consists of the step-by-step manipulation of symbols or characters, which are written to a memory tape according to certain rules and also read from there. Strings of these symbols can be interpreted in different ways, including numbers . A Turing machine thus describes a function that maps character strings that are initially on the tape to character strings that are on the tape after "processing" by the machine. A function that can be calculated using a Turing machine is called Turing-calculable or simply calculable .

Turing machines also play an important role in the acceptance of formal languages . The languages ​​that are accepted by Turing machines correspond to the languages ​​that can be defined with type 0 grammars .

Informal description

One-band Turing machine

Model of a Turing machine

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

• an infinitely long storage tape with an infinite number of sequentially arranged fields . Exactly one character from a predefined alphabet can be saved per field . A blank (English for "empty / blank") is permitted as an additional character, which corresponds to an empty field on the storage tape.
• a program- controlled read and write head that can move field by field on the storage tape and change the characters (in the case of a blank to be 'written', it can also delete it).

A calculation for an input word starts with the input word on the tape and the read and write head on the first symbol of the input word. The Turing machine then processes the input on the tape step by step according to the specified program.

With each step, the read / write head reads the current character, overwrites it with another (or the same) character and then moves one field to the left or right or stops. Which character is written and which movement is carried out depends on the character found at the current position and the state in which the Turing machine is currently located. This is defined by a transfer function belonging to the Turing machine. At the beginning, the Turing machine is in a predefined start state and changes to a new state with each step. The number of states in which the Turing machine can be is finite. A state can be run through several times; it says nothing about the characters on the tape.

A Turing machine stops if no transition to a new state is defined for the current state and the tape symbol read. So it generally depends on the combination of status and symbol whether the Turing machine continues to calculate or stops. States in which the Turing machine stops regardless of the tape symbol read are called end states. But there are also Turing machines that never stop for certain inputs.

In addition to calculating functions, the Turing machine - like many other automata - is also used for decision-making problems, i.e. for questions that can be answered with “yes” or “no”. Certain final states are defined as "accepting", others as "not accepting". The input is accepted exactly when the Turing machine ends in an accepting final state.

meaning

The mathematician Alan Turing presented the Turing machine in 1936 as part of the Hilbert program formulated by David Hilbert in 1920 specifically for solving the so-called decision problem in the publication On Computable Numbers, with an Application to the Decision Problem.

The decision problem posed by Hilbert asks whether a given formula of predicate logic is generally valid, i.e. whether the formula is true under any interpretation . Hilbert asked whether this problem can be solved automatically. The method that determines for a predicate logic formula whether it is generally valid should therefore be able to be carried out by a “machine”. Before the invention of the computer, this meant that a person would perform a calculation according to fixed rules - an algorithm.

With his model, Turing defined the terms algorithm and predictability as formal, mathematical terms. In general, it is assumed that Turing predictability meets the intuitive understanding of predictability; this statement is known as the Church-Turing thesis . You have a strong plausibility, u. a. through the mathematical equivalence of the concept of Turing computability with other computability concepts (such as expressibility in the lambda calculus or as a partially recursive function , as well as computability using register machines , which are modeled on computers that are structurally used today). The special thing about a Turing machine is its structural simplicity. It only requires three operations (reading, writing and moving the read / write head) to simulate all the operations of conventional computer programs. In the context of theoretical computer science, it is therefore particularly suitable for proving the properties of formal problems as they are considered by the complexity and predictability theory .

The complexity (such as runtime and memory complexity ) of algorithms is defined in relation to certain machine models. On Turing machines, for example, the asymptotic number of state transitions depending on the input length is a possible runtime complexity measure for an algorithm. Other models often define complexity measures that define random access to each memory cell or the execution of arithmetic operations as individual steps. These dimensions are particularly well suited to a limited extent (small amounts of data or small numbers) for estimating the runtime of many algorithms on real computers and are accordingly often encountered (especially unspecified). Because of the sequential structure of Turing machines, the runtime complexity in terms of the asymptotic number of state transitions is higher for many algorithms compared to definitions for register machines. The complexity theory deals with the question of which problems algorithms with which complexity exist, for example in which complexity classes there are problems or not. Unless polynomial factors in the input length are important when examining the runtime complexity, Turing machines can be used here quite generally, since the simulation of many register machines in many dimensions of complexity only means additional polynomial effort.

Not all mathematical functions can be calculated by a Turing machine, even if you limit yourself to well-defined functions with finite input and output (for example, functions between any real numbers cannot be represented by functions with finite input and output, since the real numbers are uncountable and, from a formal point of view, there are functions that cannot be specified at all). Turing was able to show that a Turing machine cannot solve Hilbert's decision problem, any more than can the stopping problem .

According to Rice's theorem, any non-trivial property of a program in a powerful programming language is also undecidable . Even if you limit yourself to terminating Turing machines, it is undecidable whether two terminating Turing machines accept the same language. The computability theory deals with the question of which problems are computable or not computable by which machine models.

Systems, computers and programming languages that could emulate a Turing machine by hiding the limited memory and associated properties are called Turing complete .

Formal definition

Formally, a deterministic Turing machine can be represented as a 7- tuple ( see also nondeterministic Turing machine ). ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)}$

• ${\displaystyle Q}$ is the finite set of states
• ${\displaystyle \Sigma }$is the finite input alphabet
• ${\displaystyle \Gamma }$ is the finite ribbon alphabet and it holds ${\displaystyle \Sigma \subset \Gamma }$
• ${\displaystyle \delta \colon (Q\setminus F)\times \Gamma \to Q\times \Gamma \times \{L,N,R\}}$ is the (partial) transfer function
• ${\displaystyle q_{0}\in Q}$ is the initial state
• ${\displaystyle \square \in \Gamma \setminus \Sigma }$stands for the empty field ( blank )
• ${\displaystyle F\subseteq Q}$ the set of accepting final states

The partial transfer function returns to a state and a read tape symbol (i) the next state, (ii) a tape symbol that is written in the current field, and (iii) the direction of movement of the read / write head (L .. one field after left, N .. do not move, R .. one space to the right). Since the calculation stops in any case in accepting final states, these are excluded from the definition of the transfer function. ${\displaystyle \delta }$

Configurations

Configuration of a Turing machine in the state . The read / write head is located above the symbol highlighted in gray . If you use the blank symbol of the Turing machine, this configuration corresponds to the triple ${\displaystyle q_{1}}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle (q_{1},\epsilon ,011B)}$

The configuration of a Turing machine describes not only its own current state , but also the position of the read / write head and the symbols currently on the tape. The symbols are located in a finite area of ​​the band which is surrounded by an infinite number of empty symbols. It is therefore sufficient to consider this finite area. ${\displaystyle q\in Q}$

Formally, a configuration consists of the current status , a finite word that contains the content of the tape to the left of the read / write head and a finite word that contains the contents of the tape from the current position of the read / write head. A configuration is thus a triple with , , , wherein the band through is given and the read-write head on the first character of stands. ${\displaystyle q\in Q}$ ${\displaystyle u\in \Gamma ^{*}}$ ${\displaystyle v\in \Gamma ^{*}}$ ${\displaystyle (q,u,v)}$ ${\displaystyle q\in Q}$ ${\displaystyle u\in \Gamma ^{*}}$ ${\displaystyle v\in \Gamma ^{*}}$ ${\displaystyle uv}$ ${\displaystyle v}$

Often, configurations are also described by a sequence , in which the current status is inserted at the current position of the read / write head in the word that reproduces the tape content. is the leftmost, non-empty tape symbol, the furthest right, non-empty tape symbol, and the symbol above which the read / write head is located. If the read / write head moves over the edge, additional symbols must be added to the configuration . ${\displaystyle X_{1}X_{2}\cdots X_{i-1}qX_{i}X_{i+1}\cdots X_{n}}$ ${\displaystyle X_{\ell }\in \Gamma ,q\in Q}$ ${\displaystyle q}$ ${\displaystyle X_{1}}$ ${\displaystyle X_{n}}$ ${\displaystyle X_{i}}$ ${\displaystyle \square }$

The input word is determined by a start configuration. A common start configuration is with the start status and input word . This corresponds to the triple , where the empty word is. ${\displaystyle q_{0}X_{1}\cdots X_{n}}$ ${\displaystyle q_{0}}$ ${\displaystyle X_{1}\cdots X_{n}}$ ${\displaystyle (q_{0},\epsilon ,X_{1}\cdots X_{n})}$ ${\displaystyle \epsilon }$

calculation

The transfer function specifies the sequence of a Turing machine for a start configuration. It changes from the current configuration to the successor configuration in one step. Such a step from configuration to configuration can be represented as. ${\displaystyle \delta }$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$ ${\displaystyle c_{1}\vdash c_{2}}$

Writes the transfer function for a state and the input symbol , for example, before that is written, the read-write head moves to the left and the successor state is, this means the following step: . ${\displaystyle q}$ ${\displaystyle X_{i}}$ ${\displaystyle Y}$ ${\displaystyle p}$ ${\displaystyle X_{1}\cdots X_{i-1}qX_{i}X_{i+1}\cdots X_{n}\vdash X_{1}\cdots pX_{i-1}YX_{i+1}\cdots X_{n}}$

The computation of a Turing machine is a finite or infinite series of configuration steps. A Turing machine accepts a word given by the start configuration if the computation begins in this start configuration and ends in a configuration in which the Turing machine is in an accepting end state . If the calculation ends in a different configuration, the Turing machine discards the input word. If the calculation of the Turing machine is infinite, the word is neither accepted nor rejected. ${\displaystyle q_{f}\in F}$

intuition

The Turing machine performs a computation by stepwise converting an input into 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 (one character of the input word per tape field), the rest of the tape consists of empty fields . The read / write head is on the first character of the input and the Turing machine is in the start state . ${\displaystyle \square }$ ${\displaystyle q_{0}}$

The transfer function specifies how the Turing machine reads and writes the contents of the tape step by step, changes its status and changes the position of the read / write head. This function takes the current status and the character that is located under the read / write head in the current configuration as arguments. As a result it then delivers:

• exactly one state (this becomes the successor state of the Turing machine),
• a character (this overwrites the content of the field to which the read / write head points) and
• either the symbol L (in this case the read / write head moves one field to the left), R (in this case it moves one field to the right) or N (then it remains in the same field).

The Turing machine has now gone through one step of its work cycle and is ready for another.

Since the transition function is partial, it does not have to define a transition for every state and every input character. For example, the final state has no subsequent state for any input character. If the Turing machine reaches an end state , the Turing machine cannot therefore carry out any further actions and the calculation is ended. The output is then the content of the volume. ${\displaystyle q_{f}\in F}$

example

The following deterministic single-tape Turing machine expects a sequence of ones as input on the tape. It doubles the number of ones, leaving a blank symbol in the middle. For example, “11” becomes “11011”. The read / write head is initially on the first one. The initial state is the end state . The zero stands for the empty field and the tape consists of empty fields except for the ones written on it. ${\displaystyle M}$ ${\displaystyle s1}$ ${\displaystyle s6}$ ${\displaystyle \square }$

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,s1,0,\{s6\})}$

• ${\displaystyle Q=\{s1,s2,s3,s4,s5,s6\}}$
• ${\displaystyle \Sigma =\{1\}}$
• ${\displaystyle \Gamma =\{1,0\}}$

The transfer function is defined as follows: ${\displaystyle \delta }$

The transfer function as a graph ${\displaystyle \delta }$

current state	read. symbol		schr. symbol	new condition	Head direction
s1	1	→	0	s2	R.
s1	0	→	0	s6	N
s2	1	→	1	s2	R.
s2	0	→	0	s3	R.
s3	1	→	1	s3	R.
s3	0	→	1	s4	L.
s4	1	→	1	s4	L.
s4	0	→	0	s5	L.
s5	1	→	1	s5	L.
s5	0	→	1	s1	R.

${\displaystyle M}$ runs through the following states in the example mentioned above, i.e. when entering "11", whereby the current head position is printed in bold:

The Turing machine described is applied to input “11”.

step	Condition	tape
1	s1	1 1000
2	s2	0 1 000
3	s2	01 0 00
4th	s3	010 0 0
5	s4	01 0 10
6th	s5	0 1 010
7th	s5	0 1010
8th	s1	1 1 010

step	Condition	tape
9	s2	10 0 10
10	s3	100 1 0
11	s3	1001 0
12	s4	100 1 1
13	s4	10 0 11
14th	s5	1 0 011
15th	s1	11 0 11
16	s6	-stop-

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 the new status is set . The head now moves to the right until an empty field is read. Then the Turing machine gets into the state and skips all further ones until it finds an empty field again. This is then replaced by a one. In the state the head moves back, again reading over all ones until it hits an empty field, state change on . The head now moves to the left until the empty field originally written in state is found. This is again replaced by a one, the head moves one field to the right and the Turing machine returns to the state . A new computing cycle begins here. If an empty field is read in the state , the Turing machine reaches the final state , whereupon the calculation is ended. ${\displaystyle s1}$ ${\displaystyle s2}$ ${\displaystyle s3}$ ${\displaystyle s4}$ ${\displaystyle s5}$ ${\displaystyle s1}$ ${\displaystyle s1}$
${\displaystyle s1}$ ${\displaystyle M}$ ${\displaystyle s6}$

Equivalent variants of the Turing machine

In the literature one finds numerous different definitions and variants of the Turing machine, each of which differs in some details. These are equivalent in the sense that Turing machines of one definition can easily be converted into Turing machines of the other definitions so that they perform the same calculations. Frequent deviations from the above definition are:

• No distinction is made between input alphabet and ribbon alphabet.
• Instead of a set of accepting end states, there is only one accepting end state.
• In addition to one or more accepting end states, there are also one or more rejecting end states.
• The read / write head always moves either to the left or to the right. So there are only symbols for the movement of the head . ${\displaystyle L,R}$
• The function is given as a total function. The machine stops in final states and in states when the symbol is read and . ${\displaystyle \delta }$ ${\displaystyle q\in Q}$ ${\displaystyle a}$ ${\displaystyle \delta (q,a)=(q,a,N)}$
• Semi-infinite storage band: The storage band is only infinite in one direction. There is a special symbol that marks the beginning of input. The read / write head cannot then move beyond this to the left, but as far to the right as desired.

There are also extensions that are also equivalent to Turing machines in terms of predictability. Even in terms of complexity theory , the differences between many of the variants are largely negligible. Overall, a very large number of variants lead to no more than polynomial differences in effort (effort here means any resource) and are therefore negligible for many complexity-theoretical investigations. Depending on the objectives of the respective analysis, the model used is adapted so that the analysis can be carried out as easily as possible. However, there are also equivalent extensions of the Turing machine, such as non-deterministic Turing machines and certain oracle-Turing machines, with regard to the predictability, but not the complexity (in the sense of “up to polynomial additional effort”) .

• Multi-track Turing machine (engl. Multi-track Turing machine ): Turing machines, which allow to store a plurality of symbols in a field of the storage tape.
• More Turing machine (engl. Multitape Turing machine ): Turing machines with a plurality of bands, each having a read-write head.
• Forgetful Turing machine (engl. Oblivious Turing machines ): A Turing machine is forgetful or also called motion uniform, if the head movements do not depend on the specific content of the input, but only on the length of the input. Every Turing machine can be simulated by a forgetful one.
• Two- cellar machine ( Two-stack Push Down Automaton ): A cellar machine with two cellar stores .
• Counter machinery (engl. Counter Machine ) with at least 2 meters.

Transfer function δ as an integer

In his original article on Hilbert's decision problem, Alan Turing describes a way of defining the transfer function, which is usually displayed graphically or written down in a table, using a single number. To do this, he first converts the table into a normal form and then replaces the individual states, letters and instructions with numbers, which are then combined into a long number.

Universal Turing machine

In the definition above, the program is built into the machine and cannot be changed. If the description of a Turing machine is coded as a sufficiently simple character string, a so-called universal Turing machine - even a Turing machine - can be constructed which takes such a coding of any Turing machine as part of its input and simulates the behavior of the coded Turing machine on the input that is also given. From the existence of such a universal Turing machine, for example, the undecidability of the halting problem follows . A similar idea, in which the program is viewed as part of the changeable input data, is also the basis of almost all computer architectures today ( Von Neumann architecture ).

Formally, a universal Turing machine is a machine that reads input . The word here is a sufficiently simple description of a machine that calculates the output for a specific function with input . is a separator between program description and input. simulates the behavior of with the help of the function description and the input . The index in indicates that there is not just one universal Turing machine. So could z. B. and understand different words. The word must be coded in a language that she understands. ${\displaystyle {\mathit {UTM}}_{\phi }}$ ${\displaystyle w\|x}$ ${\displaystyle w}$ ${\displaystyle M_{w}}$ ${\displaystyle x}$ ${\displaystyle \|}$ ${\displaystyle {\mathit {UTM}}_{\phi }}$ ${\displaystyle M_{w}}$ ${\displaystyle w}$ ${\displaystyle x}$ ${\displaystyle \phi }$ ${\displaystyle {\mathit {UTM}}_{\phi }}$ ${\displaystyle {\mathit {UTM}}_{1}}$ ${\displaystyle {\mathit {UTM}}_{2}}$ ${\displaystyle w}$ ${\displaystyle {\mathit {UTM}}_{\phi }}$

Well-known Turing machines

Hardworking beaver

Hardworking beaver with 2 states + final state, who writes four '1' before terminating

As Fleißige Beaver (engl. Busy Beaver ) are referred to the deterministic Turing machines based on all terminating deterministic Turing machine with the same number of states and symbols, the maximum number of write of a particular symbol on the tape and then stop. There is no calculable function that assigns a given number of symbols and states a corresponding hardworking beaver, the number of symbols he has written at the end (the so-called Radó function ) or the number of steps he needs to terminate.

ant

Chris Langton's ant is a Turing machine with a two-dimensional band (actually a surface) and very simple rules, the content of the band as a two-dimensional image initially looks chaotic, but after more than 10,000 steps it develops a certain visible structure.

Machine models based on Turing machines

Nondeterministic Turing machine

→ Main article : Nondeterministic Turing machine

A nondeterministic Turing machine uses a transition relation instead of the transition function. In the configuration of this nondeterministic Turing machine there can therefore be several possibilities for the next calculation step. The machine accepts a word when one of the possible calculations that start with the word as input reaches an acceptable end state. ${\displaystyle \delta }$

Alternating Turing machine

→ Main article : Alternating Turing machine

An alternating Turing machine is a nondeterministic Turing machine that extends the rules for accepting an input. A distinction is made between existential and universal states of the machine. The former accept input if there is a possible computation that will accept, while the second states accept input only if all possible computations are accepted.

Oracle Turing machine

→ Main article : Oracle Turing machine

Oracle Turing machines are generalizations of the Turing machine, in which the Turing machine can perform certain additional operations in one step, such as the solution of undecidable problems or problems that can only be decided with great effort. Oracle-Turing machines allow a further categorization of undecidable problems, see Turinggrad , or the definition of additional complexity classes.

Probabilistic Turing machine

→ Main article : Probabilistic Turing machine

Probabilistic Turing machines allow two (or, equivalently, finitely many) possible transitions for every state and every input, one of which is selected at random during execution - to put it intuitively - and serve the theoretical description of randomized algorithms .

Quantum Turing machine

Quantum Turing machines serve in quantum informatics as abstract machine models for the theoretical description of the possibilities of quantum computers . In this context, quantum circuits are another popular model.

Persistent Turing machine

In order to represent interactive models (in the sense of “models with memory”) by a Turing machine, it is necessary to expand them to include this memory.

According to the definition, a persistent Turing machine (PTM) is a nondeterministic 3-band Turing machine with an input, a working and an output band. The input is processed on the work belt, and only after it has been completely processed do the results return to the "environment" on the output belt. A new input from the environment can then be processed. The contents of the work volume are retained as a “memory” between two work steps.

Zeno machine

→ Main article : Zeno machine

The Zeno machine is a Turing machine that calculates faster and faster in a geometric series. It represents a fictional model beyond the Turing predictability.

Relationship between a Turing machine and a formal language

Accepted language

A Turing machine accepts a language if it stops in an acceptable state after a finite number of steps when entering every word and if it stops in an unacceptable state or not at all when entering every word . ${\displaystyle L}$ ${\displaystyle x\in L}$ ${\displaystyle x\not \in L}$

A language is called recursively enumerable or semi-decidable (type 0 of the Chomsky hierarchy ) if and only if there is a Turing machine that accepts it. ${\displaystyle L\subseteq \Sigma ^{\star }}$ ${\displaystyle L}$

Decidable language

If a Turing machine accepts a language and also keeps it for all inputs that do not belong to this language, the Turing machine decides this language.

A language is called recursive or decidable if and only if there is a Turing machine that decides. ${\displaystyle L\subseteq \Sigma ^{\star }}$ ${\displaystyle L}$

literature

• Rolf Herken (Ed.): The Universal Turing Machine. A Half-Century Survey (=  computer culture . Volume 2 ). 2nd Edition. Springer, Vienna a. a. 1995, ISBN 3-211-82637-8 .
• Juraj Hromkovič : Theoretical Computer Science. Formal languages, predictability, complexity theory, algorithms, communication and cryptography . 3rd, revised and expanded edition. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0043-5 .
• John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman : Introduction to Automata Theory, Languages, and Computation . 2nd Edition. Addison-Wesley, Boston MA a. a. 2001, ISBN 978-0-201-44124-6 .
• Sybille Krämer : Symbolic machines. The idea of ​​formalization in a historical outline. Scientific Book Society, Darmstadt 1988, ISBN 3-534-03207-1 .
• Heinz Lüneburg : Recursive functions . Springer, Berlin a. a. 2002, ISBN 3-540-43094-6 .
• Marvin L. Minsky : Computation. Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs NJ 1967.
• Charles Petzold : The Annotated Turing. A guided tour through Alan Turing's historic Paper on Computability and the Turing Machine. John Wiley & Sons, Indianapolis IN 2008, ISBN 978-0-470-22905-7 .
• Boris A. Trachtenbrot : Algorithms and Calculators. VEB Deutscher Verlag der Wissenschaften Berlin 1977.
• Alan Turing: On Computable Numbers, with an Application to the Decision Problem . In: Proceedings of the London Mathematical Society . tape 42 , 1937, ISSN  0024-6115 , pp. 230-265 , doi : 10.1112 / plms / s2-42.1.230 ( Oxford Journals ).
• Oswald Wiener , Manuel Bonik, Robert Hödicke: An elementary introduction to the theory of Turing machines . Springer, Vienna a. a. 1998, ISBN 3-211-82769-2 .

Web links

Commons : Turing machines  - collection of images, videos and audio files

Wiktionary: Turing machine  - explanations of meanings, word origins, synonyms, translations

• David Barker-Plummer:  Turing Machines. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
• Georg Weuffen: The Turing machine . In: MathePrisma multimedia project of the Bergische Universität Wuppertal
• Turing machines on informatikseite.de
• Single-band / multi-band -Turingmaschine: Simulation of basic arithmetic (JavaScript)
• Website about a physical Turing machine (including video)
• elstel.org/coan/ Turingsimulator: a program that can also simulate non-deterministic Turing machines and machine schemes

Individual evidence

1. ↑ ^{a b} Juraj Hromkovič : Theoretical Computer Science . Formal languages, predictability, complexity theory, algorithms, communication and cryptography. 3. Edition. BG Teubner Verlag, Heidelberg 2007, ISBN 978-3-8351-0043-5 .
2. Jump up ↑ John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory. 3rd, updated edition. Pearson Studium, Munich 2011, ISBN 978-3-86894-082-4 .
3. ↑ Ingo Wegener : Theoretical Computer Science. An algorithm-oriented introduction . BG Teubner, Stuttgart, ISBN 3-519-02123-4 .
4. ↑ in English: oblivious, see Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, Cambridge / New York 2009, ISBN 978-0-521-42426-4 , pp. 45 ( princeton.edu [PDF; accessed June 13, 2013]).
5. ↑ Karl Rüdiger Reischuk: Complexity Theory . 2nd Edition. Volume I: Basics . Teubner, 1999, ISBN 978-3-519-12275-3 , pp. 103 .
6. ^ Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach . Cambridge University Press, Cambridge / New York 2009, ISBN 978-0-521-42426-4 , pp. 19 ( princeton.edu [PDF; accessed June 13, 2013] Remark 1.10).
7. Jump up ↑ John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory. 3rd, updated edition. Pearson Studium, Munich 2011, ISBN 978-3-86894-082-4 , 8.5.3 Counter machines 8.5.4 The performance of counter machines.
8. ^ Alan Turing: On Computable Numbers, with an Application to the Decision Problem. November 1936, p. 8-10 .
9. ^ Entry on the probabilistic Turing machine on the NIST website
10. ↑ Goldin et al., 2003: Turing Machines, Transition Systems and Interaction