Multi-Tape Turing Machine

Formal Definitionε

A k-tape Turing Machine is M = $(Q, Σ, Γ, δ, q0, q_{acc}, q_{rej})$ where

Q is a finite set of control states

Σ is a finite set of input symbols

F ϽΣ is a finite set of tape symbols. Also, a blank symbol ϵΓ\ Σ

q0 ϵQ is the initial state

q_{acc}ϵQis the accept state

q_{rej}ϵQ is the reject state, where q_{acc} and q_{rej} are not equal

$δ: (Q \ {q_{acc}, q_{rej}}) X Γ^K Q (ΓX{ L, R})^K$ is the transition function

Overall construction:

1. First the machine will rewrite input w to be in \new" format.

2. To simulate one step

Read from left-to-right remembering symbols read on each tape, and move all the way back to leftmost position.

Read from left-to-right, changing symbols, and moving those heads that need to be moved right.

Scan back from right-to-left moving the heads that need to be moved left.

Formally, let M = $(Q, Σ, Γ, δ, q0, q_{acc}, q_{rej})$ .To define the machine single(M) it is useful to identify modes that single(M) could be in while simulating M. The modes are mode = {init, back-init, read, back-read, fix-right, fix-left} where

init means that the machine is rewriting input in new format

back-init means the machine is just going back all the way to the leftmost cell after initializing the tape

read means the machine is scanning from left to right to read all symbols being read by k-tape machine

back-read means the machine is going back to leftmost cell after the \read" phase

x-right means the machine is scanning from left to right and is going to make all tape changes and move those heads that need to be moved right

x-left means the machine is scanning right to left and moving all heads that need to be moved left

Non-Deterministic Turing Machine

It is a Turing Machine which has finitely many possibilities at each step.

So, formally M = $(Q, Σ, Γ, δ, q0, q_{acc}, q_{rej})$

where

$Q, Σ, Γ, q0, q_{acc}, q_{rej}$ are same as that of 1-tape Turing machine

$δ: (Q \ {q_{acc}, q_{rej}}) X Γ^K -\gt P(Q XΓX{ L, R})^K$

Execution of det(M), which means deterministic Turing Machine

1. Initially: Input tape contains w, simulation tape and choice tape are blank

2. Copy contents of input tape onto simulation tape

3. Simulate M using simulation tape as its (only) tape

(a) At the next step of M, if state is q, simulation tape head reads X, and choice tape head readsi, then simulate the ith possibility in _(q;X); if i is not a valid choice, then goto step 4

(b) After changing state, simulation tape contents, and head position on simulation tape, move choice tape's head to the right. If Tape 3 is now scanning t, then goto step 4

(c) If M accepts then accept and halt, else goto step 3(1) to simulate the next step of M. 4. Write the lexicographically next choice sequence on choice tape, erase everything on simulation tape and goto step 2.

Random Access Machine

Instruction Set

add X, Y: Add the contents of registers X and Y and store the result in X.

load c X, I: Place the constant I in register X.

load X, M: Load the contents of memory location M into register X.

loadI X, M: Load the contents of the location \pointed to" by the contents of M into register X.

store X, M: store the contents of register X in memory location M.

jmp M: The next instruction to be executed is in location M.

jmz X, M: If register X is 0, then jump to instruction M.

halt: Halt execution.