Note that a real-time Turing machine runs in time n (it must read a symbol from the input tape at each step and give a result at its end).
Example 1: A simple example could be:
Input: $L =\{ w\#w \} $
$L$ can be recognized by a 2-tape (input+work) TM in linear time, but not by a (k-tape) real-time TM.
Example 2: A more "proof-friendly" example could be:
$L = \{ x \# 0^m \mid m \leq |x| \text{ and the m-th bit of x is 1 } \}$.
A 2-tape (input+work) TM can recognize $L$ in linear time, but a 2-tape real-time TM cannot.
A proof sketch could follow this line:
- suppose that such real-time TM $M$ exists
- pick a long enough incompressible string $w = x_1 x_2 x_3 x_4 x_5 x_6$ with $|x_i| = k$
- run $M$ on input $w \#$ and when the first head reaches the $\#$ consider the content $y = y_1 y_2 y_3 y_4 y_5 y_6, |y_i| = k$ of the second tape, the current state $Q$ of $M$ and the second head position $h_2$.
Notice that when run on different inputs $w \neq w' \;, |w| = |w'|$ the resulting $\langle y, Q, h_2 \rangle$, $\langle y', Q', h_2' \rangle$ must be different because $M$ cannot go back on the input, so it must decide each bit of it using the current content of the second tape, state and head 2 position.
We have the following cases:
- the second head didn't reach $y_6$, so $y_6$ is "blank"
- the second head reached $y_6$; in this case its current position is on $y_6$ or $y_5$ (the second head after reaching $y_6$ don't have enough "time" to go back to $y_4$ before head 1 reaches the $\#$)
Suppose we are in case 2; if the computation of $M$ continues for $2k$ steps, the second head starting from $y_5 y_6$ cannot reach $y_2$, so we can reconstruct the first $2k$ bits of $w$: $x_1 x_2$ from the partial string $y_2 y_3 y_4 y_5 y_6$.
Now we can simulate $M$ on $x_1 x_2$ for $2k$ steps and we are sure that the resulting $y_1'$ (first $k$ cells of the second tape) is the "final" version; i.e. $y_1' = y_1$ otherwise if the head is still on $y_1'$ it would not be able to reach $y_6$ (which is the assumption of the current case).
So in both case we are able to reconstruct the full content of $y$ from a substring of length $5k$, the position of $h_2$ ($\log(6k)$), $Q$ and the description of $M$ (constant $c$).
$y_1 y_2 y_3 y_4 y_5 \to y_1 y_2 y_3 y_4 y_5 [\text{blank}] = y$ in the first case
$ y_2 y_3 y_4 y_5 y_6 \to [y_1'] y_2 y_3 y_4 y_5 y_6 = y $ in the second case
But now we can run $M$ on all strings $x$ of length $6k$ , and check which one leads to $\langle y, Q, h_2\rangle$ after $6k+1$ steps.
So we would be able to reconstruct $w$ using
$5k + log(6k) + c $
bits, which for great enough $k$ is less than $|w| = 6k$, which is in contradiction with the assumption that $w$ is incompressible.
Note that the Example 1 could also be proved with the same technique with only minor differences.
