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

CC BY-SA 4.0
2023-03-28T18:56:11.573Z
Nice! Where can I find a proof that $L$ cannot be recognized by a real-time TM?
QMath
CC BY-SA 4.0
2023-03-28T20:59:28.453Z
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.
Marzio De Biasi
CC BY-SA 4.0
2023-03-29T14:25:26.813Z
I added another example with a possible proof sketch. Didn't think about it too much, so perhaps it doesn't work.
Marzio De Biasi
CC BY-SA 4.0
2023-03-29T17:47:15.270Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-03-29T18:28:14.623Z
@EmilJeřábek I see, the sketch is a bit confused, the idea is that you can also rerun M on the discovered original input and guess (scan) the unknown part until the computation of M after $3k$ step is equal to the one encoded by $z$ (which must uniquely identify the input $w$). I'll try to explain it better. And perhaps if $m$ is in binary it would be even simpler.
Marzio De Biasi
CC BY-SA 4.0
2023-03-30T14:17:04.000Z
@EmilJeřábek: I tried to modify the proof, now it should be more clear (not sure if there are things I  missed and that make it wrong). And perhaps expressing $m$ in binary would not work, because in that case a standard 2-tape TM cannot decide the language in linear time .
Marzio De Biasi
CC BY-SA 4.0
2023-03-30T15:26:31.430Z
I haven’t yet had the time to look at the update in detail. But with $m$ in binary, the language is certainly computable in linear time, that’s quite straightforward: copy $m$ to the work tape, rewind the input tape back to the start, and keep decrementing the number on the work tape while moving the input head to locate the $m$th bit. It is well known that this kind of binary counter works in time $O(m)$. The only issue is that $m$ can, in fact, be much larger than $|x|$. To fix this, first use a binary counter to compute the length of $x$ in binary on the work tape while moving the input ...
Emil Jeřábek
CC BY-SA 4.0
2023-03-30T15:29:14.827Z
... head towards $\#$. Then overwrite the work tape with a copy of $m$ while making sure that the length of $m$ does not exceed the length of the binary representation of $|x|$ (otherwise reject); this ensures that $m<2|x|$, hence the rest of the algorithm will run in time $O(|x|)$.
Emil Jeřábek
CC BY-SA 4.0
2023-03-30T15:39:03.940Z
(Or, of course, you can check $m\le|x|$ exactly before copying it to the work tape, by reading it twice. But this will not improve the running time.)
Emil Jeřábek
CC BY-SA 4.0
2023-03-30T15:46:43.897Z
@EmilJeřábek: right, I forgot that the binary $\leftrightarrow$ unary conversion is linear (w.r.t. the length of the unary string) on a 2-tape TM. In any case even with $m$ in unary the proof should work, let me know if you find errors.
Marzio De Biasi
CC BY-SA 4.0
2023-04-03T10:11:42.877Z
I think it works.
QMath
CC BY-SA 4.0
2023-03-28T17:03:12.943Z
2023-04-03T15:20:49.087Z
2023-04-03T15:20:49.087Z
Marzio De Biasi
<p>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.</p>
<p>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.</p>
<p>[1] Rosenberg, Arnold L.. “Real-Time Definable Languages.” J. ACM 14 (1967): 645-662.</p>

CC BY-SA 4.0
2023-03-28T10:22:21.457Z
Could you share some exact references to the "old" proofs you are referring to?
J.y B.y
CC BY-SA 4.0
2023-03-28T11:07:53.780Z
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.
QMath
CC BY-SA 4.0
2023-03-29T09:12:08.337Z
I meant, in your question, not for me :)
J.y B.y
<cc.complexity-theory><reference-request><turing-machines>
Examples for Real-time vs Linear time
QMath
# Examples for Real-time vs Linear time

(Asked by: username_0 on 2023-03-27)

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.

**Tags:** cc.complexity-theory, reference-request, turing-machines

> **Comments:**
> **username_1**: Could you share some exact references to the "old" proofs you are referring to?  
> **username_0**: 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.  
> **username_1**: I meant, in your question, not for me :)  

---

## 1 answers

### Answer by username_2 on 2023-03-28. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Nice! Where can I find a proof that $L$ cannot be recognized by a real-time TM?  
> **username_2**: 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.  
> **username_2**: I added another example with a possible proof sketch. Didn't think about it too much, so perhaps it doesn't work.  
> **username_3**: 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.  
> **username_2**: @EmilJeřábek I see, the sketch is a bit confused, the idea is that you can also rerun M on the discovered original input and guess (scan) the unknown part until the computation of M after $3k$ step is equal to the one encoded by $z$ (which must uniquely identify the input $w$). I'll try to explain it better. And perhaps if $m$ is in binary it would be even simpler.  
> **username_2**: @EmilJeřábek: I tried to modify the proof, now it should be more clear (not sure if there are things I  missed and that make it wrong). And perhaps expressing $m$ in binary would not work, because in that case a standard 2-tape TM cannot decide the language in linear time .  
> **username_3**: I haven’t yet had the time to look at the update in detail. But with $m$ in binary, the language is certainly computable in linear time, that’s quite straightforward: copy $m$ to the work tape, rewind the input tape back to the start, and keep decrementing the number on the work tape while moving the input head to locate the $m$th bit. It is well known that this kind of binary counter works in time $O(m)$. The only issue is that $m$ can, in fact, be much larger than $|x|$. To fix this, first use a binary counter to compute the length of $x$ in binary on the work tape while moving the input ...  
> **username_3**: ... head towards $\#$. Then overwrite the work tape with a copy of $m$ while making sure that the length of $m$ does not exceed the length of the binary representation of $|x|$ (otherwise reject); this ensures that $m<2|x|$, hence the rest of the algorithm will run in time $O(|x|)$.  
> **username_3**: (Or, of course, you can check $m\le|x|$ exactly before copying it to the work tape, by reading it twice. But this will not improve the running time.)  
> **username_2**: @EmilJeřábek: right, I forgot that the binary $\leftrightarrow$ unary conversion is linear (w.r.t. the length of the unary string) on a 2-tape TM. In any case even with $m$ in unary the proof should work, let me know if you find errors.  
> **username_0**: I think it works.  

---

