Prove there exists a recursive language which no TM accepts in n steps.

Question

There is a problem I can't solve: Assume n is an integer. Prove that there exists a recursive language such that there is no Turing Machine which accepts it and makes a maximum of n steps for every input. I'll be glad to receive hints. Thanks!

Note that this has been cross-posted at MO, although it looks likely to be closed there. — Old John, Dec 29 '12 at 15:55

score 0 · Accepted Answer · answered Dec 29 '12 at 15:50

0

Hint: In $n$ steps, a Turing machine can read from at most the first $n$ cells. So any Turing machine with this property depends only on the contents of the first $n$ cells of the input tape.

answered Dec 29 '12 at 15:50

Thomas Andrews

177,126

Prove there exists a recursive language which no TM accepts in n steps.

1 Answers1