2
$\begingroup$

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!

  • 0
    Note 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 1

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.