2
$\begingroup$

A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-time. The references with such examples, that I can find, are quite old and difficult to follow. Could you suggest simple example or nice reference.

My fist attept was to consider palindromes, which is solvable in linear time by a multitape Turing machine but requires quadratic time for a single tape. However, palindromes can be recognized in real time.

[1] Rosenberg, Arnold L.. “Real-Time Definable Languages.” J. ACM 14 (1967): 645-662.

$\endgroup$
3
  • $\begingroup$ Could you share some exact references to the "old" proofs you are referring to? $\endgroup$
    – J..y B..y
    Mar 28, 2023 at 10:22
  • $\begingroup$ Rosenberg, Arnold L.. “Real-Time Definable Languages.” J. ACM 14 (1967): 645-662. I am looking for possibly more natural examples with a complete proof. It would be nice to see different techniques to proof that some language is not real-time. $\endgroup$
    – QMath
    Mar 28, 2023 at 11:07
  • $\begingroup$ I meant, in your question, not for me :) $\endgroup$
    – J..y B..y
    Mar 29, 2023 at 9:12

1 Answer 1

2
$\begingroup$

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:

  1. the second head didn't reach $y_6$, so $y_6$ is "blank"
  2. 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.

$\endgroup$
11
  • $\begingroup$ Nice! Where can I find a proof that $L$ cannot be recognized by a real-time TM? $\endgroup$
    – QMath
    Mar 28, 2023 at 18:56
  • $\begingroup$ Sorry, I only gave an example following the intuition. A formal proof is probably not trivial. For a 2-tape real time TM, I would try with the communication complexity argument, I'll think more about it. $\endgroup$ Mar 28, 2023 at 20:59
  • $\begingroup$ I added another example with a possible proof sketch. Didn't think about it too much, so perhaps it doesn't work. $\endgroup$ Mar 29, 2023 at 14:25
  • $\begingroup$ I can't follow the argument. If $M$ countinues for at most $k$ steps, you will only reconstruct the first $k$ bits of $w$, or am I confused? I am willing to believe the result if you encode $m$ in binary rather than unary, as then you will only need to continue for $\log(3k)$ steps. $\endgroup$ Mar 29, 2023 at 17:47
  • 2
    $\begingroup$ I think it works. $\endgroup$
    – QMath
    Apr 3, 2023 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.