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!
Prove there exists a recursive language which no TM accepts in n steps.
2
$\begingroup$
computability
-
0Note that this has been [cross-posted at MO](http://mathoverflow.net/questions/117522/), although it looks likely to be closed there. – 2012-12-29
1 Answers
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.