# Turing machine that can move right only $O(1)$ steps beyond input

I need to prove that a Turing machine that can move only $$k$$ steps on the tape after the last latter of the input word is not equal to a normal Turning machine.

My idea is that given a finite input with a finite alphabet the limited machine can write only a finite number of "outputs" on the tape while a normal Turing machine has infinite tape so it can write infinite "outputs" but I have no idea how to make it into a formal proof.

• – greybeard May 24 at 7:14

Your machine uses $$n + k = O(n)$$ space. As such, it can be simulated by a linear bounded automaton. The latter is known to be weaker than a general Turing machine. For example, it cannot solve the halting problem for machines using $$n^2$$ space, a problem that Turing machines are able to solve.