Multi-band Turing machine

A multi-band Turing machine ( English Multitape Turing machine ) is an abstract machine in the theoretical computer science and an expansion of the classical Turing machine .

3-band Turing machine

The multi-band Turing machine has several storage bands, each with its own read and write head, whereby these read and write heads can be moved independently of one another (a significant difference to the multi-track Turing machine ). Otherwise, a multi-band Turing machine behaves exactly like a classic Turing machine.

A multi-belt Turing machine with only one belt corresponds exactly to the classic Turing machine and every multi-belt Turing machine can be simulated by a classic Turing machine (with only one belt). The two machine models are therefore equivalent in terms of the predictability of functions, i.e. That is, both models can calculate the same functions.

The multi-band Turing machine is generally more efficient than a single-band machine, but not critical in terms of the most important questions of complexity theory , i.e. That is, especially for the question of which problems can be solved in polynomial time: A multi-band machine that solves a problem in polynomial time can be simulated by a single-band machine in polynomial time, but in general the degree of the limitation of the running time Polynomial is higher.

Formal definition

Formally, a ( deterministic ) k-band Turing machine can be represented as a tuple . ${\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 ^{k}\to Q\times \Gamma ^{k}\times \{L,N,R\}^{k}}$ 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 final states.

The definition differs from that of a classic Turing machine (or a multi-track Turing machine) only in the definition of the transfer function . The transfer function returns to a state and the k tape symbols read from the different tapes (i) the next state, (ii) k tape symbols that are written in the current field, and (iii) the k directions of movement of the read / write heads ( L… one space to the left, N… do not move, R… one space to the right). In contrast to the classic Turing machine, k symbols are read and written instead of just one symbol and k read / write heads are moved. It differs from the multi-track Turing machine in that k defines directions of movement (one for each read-write head), while with multi-track Turing machines only one direction of movement is defined for the read-write head, which moves in the same way on all tracks. ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \delta }$

In order to define a nondeterministic variant of the k-band Turing machine, the transfer function is replaced by a transition relation : ${\displaystyle \delta }$

• ${\displaystyle \delta \subseteq (Q\setminus F)\times \Gamma ^{k}\times Q\times \Gamma ^{k}\times \{L,N,R\}^{k}}$

example

The following example is a 3-band Turing machine that adds two binary numbers. At the beginning, the two given numbers are stored on the first two bands and the output is stored on the third band. ${\displaystyle M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,b\},\delta ,q_{0},b,\{q_{f}\})}$

The transfer function will be gradually defined. In the state , the machine moves the read / write heads of the first two bands to the right end of the input. When the machine has left the state , the read / write heads are on the last digit of the input. ${\displaystyle \delta }$ ${\displaystyle q_{0}}$ ${\displaystyle q_{0}}$

current state	read. symbol				schr. symbol			new condition	Head directions
${\displaystyle q_{0}}$	b	0	b	→	b	0	b	${\displaystyle q_{0}}$	N	R.	N
${\displaystyle q_{0}}$	b	1	b	→	b	1	b	${\displaystyle q_{0}}$	N	R.	N
${\displaystyle q_{0}}$	0	b	b	→	0	b	b	${\displaystyle q_{0}}$	R.	N	N
${\displaystyle q_{0}}$	0	0	b	→	0	0	b	${\displaystyle q_{0}}$	R.	R.	N
${\displaystyle q_{0}}$	0	1	b	→	0	1	b	${\displaystyle q_{0}}$	R.	R.	N
${\displaystyle q_{0}}$	1	b	b	→	1	b	b	${\displaystyle q_{0}}$	R.	N	N
${\displaystyle q_{0}}$	1	0	b	→	1	0	b	${\displaystyle q_{0}}$	R.	R.	N
${\displaystyle q_{0}}$	1	1	b	→	1	1	b	${\displaystyle q_{0}}$	R.	R.	N
${\displaystyle q_{0}}$	b	b	b	→	b	b	b	${\displaystyle q_{1}}$	L.	L.	N

The two states and are used for the actual addition . Here corresponds to the addition at the current position without a carry bit from the previous step and the addition with a carry bit from the last step. Finally we define for and . ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle \delta }$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$

current state	read. symbol				schr. symbol			new condition	Head directions
${\displaystyle q_{1}}$	b	0	b	→	b	0	0	${\displaystyle q_{1}}$	N	L.	L.
${\displaystyle q_{1}}$	b	1	b	→	b	1	1	${\displaystyle q_{1}}$	N	L.	L.
${\displaystyle q_{1}}$	0	b	b	→	0	b	0	${\displaystyle q_{1}}$	L.	N	L.
${\displaystyle q_{1}}$	0	0	b	→	0	0	0	${\displaystyle q_{1}}$	L.	L.	L.
${\displaystyle q_{1}}$	0	1	b	→	0	1	1	${\displaystyle q_{1}}$	L.	L.	L.
${\displaystyle q_{1}}$	1	b	b	→	1	b	1	${\displaystyle q_{1}}$	L.	N	L.
${\displaystyle q_{1}}$	1	0	b	→	1	0	1	${\displaystyle q_{1}}$	L.	L.	L.
${\displaystyle q_{1}}$	1	1	b	→	1	1	0	${\displaystyle q_{2}}$	L.	L.	L.
${\displaystyle q_{1}}$	b	b	b	→	b	b	b	${\displaystyle q_{f}}$	R.	R.	R.

current state	read. symbol				schr. symbol			new condition	Head directions
${\displaystyle q_{2}}$	b	0	b	→	b	0	1	${\displaystyle q_{1}}$	N	L.	L.
${\displaystyle q_{2}}$	b	1	b	→	b	1	0	${\displaystyle q_{2}}$	N	L.	L.
${\displaystyle q_{2}}$	0	b	b	→	0	b	1	${\displaystyle q_{1}}$	L.	N	L.
${\displaystyle q_{2}}$	0	0	b	→	0	0	1	${\displaystyle q_{1}}$	L.	L.	L.
${\displaystyle q_{2}}$	0	1	b	→	0	1	0	${\displaystyle q_{2}}$	L.	L.	L.
${\displaystyle q_{2}}$	1	b	b	→	1	b	0	${\displaystyle q_{2}}$	L.	N	L.
${\displaystyle q_{2}}$	1	0	b	→	1	0	0	${\displaystyle q_{2}}$	L.	L.	L.
${\displaystyle q_{2}}$	1	1	b	→	1	1	1	${\displaystyle q_{2}}$	L.	L.	L.
${\displaystyle q_{2}}$	b	b	b	→	b	b	1	${\displaystyle q_{f}}$	R.	R.	N

As an example we consider the addition of 11 and 1010.

step	Condition	Tapes
1	${\displaystyle q_{0}}$	b 1 1b
		b 1 010b
		bbbb b
2	${\displaystyle q_{0}}$	b1 1 b
		b1 0 10b
		bbbb b
3	${\displaystyle q_{0}}$	b11 b
		b10 1 0b
		bbbb b
4th	${\displaystyle q_{0}}$	b11 b
		b101 0 b
		bbbb b
5	${\displaystyle q_{0}}$	b11 b
		b1010 b
		bbbb b
6th	${\displaystyle q_{1}}$	b1 1 b
		b101 0 b
		bbbb b

step	Condition	Tapes
7th	${\displaystyle q_{1}}$	b 1 1b
		b10 1 0b
		bbb b 1
8th	${\displaystyle q_{2}}$	b 11b
		b1 0 10b
		bb b 01b
9	${\displaystyle q_{1}}$	b 11b
		b 1 010b
		b b 101b
10	${\displaystyle q_{1}}$	b 11b
		b 1010b
		b 1101b
holds	${\displaystyle q_{f}}$	b 1 1b
		b 1 010b
		b 1 101b

literature

• 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.4. Extensions for the simple Turing machine (English: Introduction to Automata Theory, Languages, and Computation . 2007. Translated by Sigrid Richter and Ingrid Tokar).
• Ingo Wegener : Theoretical Computer Science . An algorithm-oriented introduction. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 2. Turing machines, Church's thesis and decidability.
• Sanjeev Arora , Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge; New York 2009, ISBN 978-0-521-42426-4 , 1.2. The Turing Machine ( Draft [PDF; accessed July 30, 2016]).