Decidability problem and Turing machine

38 Views Asked by At

A: {[M,w], where M is Turing Machine and w is input}

M don’t move it’s head to the left and to the right.

How many iterations I need to wait to say that M is looped?

1

There are 1 best solutions below

2
On

You must wait at most as the product of number of states and number of letters in alphabet, this is because the state of tonly changes in one cell, and using pigeonhole principle after passing $k\cdot n$ iterations (let's say alphabet has $n$ letters and machine has $k$ states) there must be two iterations in which the content of the cell is same, the state of machine is the same, and therefore these are completely identical states and tapes, and that's the loop, because we can surly say after the same states and tapes, the machine performs the same action.