Question

Turing machine A that does the following:

• On its first and second tape, A receives two strings w and v, w, v ∈ {0, 1}? , representing two integer numbers. When machine A is started, the tape heads are located on the left-most position, on the most significant bits of w and v.

• If none of the inputs w and v is the empty word, the Turing machine A writes the binary representation of the sum of the two integer numbers w and v on the third tape and then accepts the input. If one of w or v is the empty word, the Turing machine does not write anything on the third tape and rejects the input. If machine A outputs something, it outputs the binary representation of the sum in such a way that the left-most bit contains the most significant bit of the sum. Be careful: w and v may be of different length.

Q: Define a 3-tape Turing machine M that implements multiplication, in a manner similar to how A implements addition

Answer 1

3-tape Turing machine M that implements multiplication

• Infinitely long tape, divided into cells, for memory

• Tape initially contains input string followed by all blanks

• Tape head (↓) can move both right and left

• Can read from and write to tape

• Finite control based on current state, current symbol that head reads from tape.

• Machine has one accept state and one reject state.

• Machine can run forever: infinite loop

• The multi-tape Turing machine has multiple tapes and multiple heads

• Each tape controlled by separate head

• Multi-Tape Multi-head Turing machine can be simulated by standard Turing machine.

• It has multi-dimensional tape where head can move any direction that is left, right, up or down.

• Multi dimensional tape Turing machine can be simulated by one-dimensional Turing machine

• It has multiple tapes and controlled by a single head

• The Multi-tape Turing machine is different from k-track Turing machine but expressive power is same.

• Multi-tape Turing machine can be simulated by single-tape Turing machine.