Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$ and blank)?

(From comments below by the OP) Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$.

-

7
Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$. – Emanuele Viola Feb 14 '11 at 23:55

4
@Emanuele: You should edit the question and emphasise this aspect; otherwise it sounds exactly like a standard textbook exercise... – Jukka Suomela Feb 15 '11 at 0:11

3
@Tsuyoshi, I think you misunderstood the question. – Suresh Venkat♦ Feb 15 '11 at 0:31

4
@Jukka: On a one-tape Turing machine, everything that can be computed in time $o(n \log n)$ are in fact regular languages. – Kristoffer Arnsfelt Hansen Feb 15 '11 at 6:37

6
@Abel: The result you quote from Arora and Barak gets around the main issue here because in their model (which is fairly standard for multi-tape TMs), they have a separate, read-only input tape. – Joshua Grochow Feb 16 '11 at 5:43
show 11 more comments

2 Answers

A partial answer if TM runs in $o( |x| \log |x|)$

If TM4 is a 4-symbols TM (with alphabet $\Sigma_4 = \{\epsilon,0,1,2 \}$ ) that computes $f:\{0,1\}^* \to \{0,1\}$, i.e. decides language $L = \{ x | f(x) = 1 \}$ in $(o( |x| \log |x|))$

One tape deterministic linear-time complexity is $1DLIN = 1DTime(O(n))$

• Hennie proved (1) that $REG = 1DLIN$
• Kobayashi proved (2) that $REG = 1DTime(o(n \log n))$

So $L$ is regular, and is obviously still regular over alphabet $\Sigma_3 = \{\epsilon,0,1\}$

So there is a DFA that decide L and uses only symbols in $\Sigma_3$. A one-tape, 3-symbols TM3 can be built directly from the DFA and it decides L using the same unpadded input of the original TM4.

... you cannot build it directly from TM4, but TM3 exists.

If TM4 runs in $\Omega(n^2)$ then you can shift the input and make a direct conversion from TM4 to TM3.

As noticed in the comments the difficult case is when TM4 runs in $\Omega(n\log n) \cap o(n^2)$.

(1) Hennie, One-tape, off-line Turing machine computations (1965)

(2) Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy (1985)

-

1
The point about $o(n\log n)$ is already noted by Kristoffer Arnsfelt Hansen in the comments below the question. The really interesting case is $\Omega(n\log n) \cap o(n^2)$. – Kaveh♦ Feb 19 '11 at 5:56
You're right I didn't noticed Kristoffer comment. I badly expressed the interesting case (I don't know how to prove it), so I updated the answer. – Marzio De Biasi Feb 19 '11 at 13:39

1
@Kaveh: What about $o(n \log n)$-time machines for promise problems? Do we already know how to convert, e.g., any machine that solves a promise problem in $O(n)$ time? I don't see how to do it, and the connection to regular languages no longer holds (unless I'm badly mistaken). – Jukka Suomela Feb 19 '11 at 16:35

1
@Kaveh: Can't you simply take a problem $L$ that is not a regular language but can be solved with a Turing machine in, e.g., $O(n^2)$ rounds, and define a promise problem as follows: yes-instances consist of a string $x \in L$ followed by $|x|^2$ bits of padding; no-instances consist of a string $x \notin L$ followed by $|x|^2$ bits of padding. The promise problem is solvable in $O(n)$ time, and it is not solvable using a finite state machine. – Jukka Suomela Feb 20 '11 at 23:04

1
@Kaveh: I guess the intuitive argument fails because of the following reason: Yes, there is a non-promise problem that is solved by the same machine. However, the running time of the machine may be as high as $\Theta(n^2)$ for certain inputs. (Intuitively, the machine cannot verify that there is enough padding, and hence "to play safe" it must assume that there is enough padding after the prefix $x$. Then it wastes $\Theta(|x|^2)$ time to determine if $x \in L$, and this is too much if, e.g., we had only $\Theta(|x|)$ bits of padding.) – Jukka Suomela Feb 20 '11 at 23:19
show 3 more comments

For all alphabet sizes greater than $1$, runtimes only change by a constant factor since $\log_k(x) \in \Theta(\log_l(x))$ for all $k, l > 1$.

Elaboration: In $t$ timesteps, the assumed Turing machine can process at most $t$ positions/bits. Bits are taken from a $k$-nary alphabet, wlog $\{0,1,\dots,k-1\}$. Create a new Turing machine by replacing every transition by $\lceil \log_2(k) \rceil$ transitions; every old bit is encoded by $\lceil \log_2(k) \rceil$ bits in $\{0,1\}$ (blanks are reserved to mark unused cells). Note this is essentially binary coded digits.

Obviously, the resulting Turing machine executes at most $\lceil \log_2(k) \rceil \cdot t \in \mathcal{O}(t)$ steps.

Addition: Above argumentation breaks because operations that overwrite an input symbol with a bit not in $\{0,1\}$ can not be translated directly; the input has to be shifted. This can be amended by translating the original input before starting computation (essentially padding); this can be done in time $\mathcal{O}(n^2)$, resulting in a total runtime of $\mathcal{O}(n^2) + \lceil \log_2(k) \rceil \cdot t$.

Consequently, using only two symbols for encoding intermediate results is of no asymptotic impact if $t(n) \in \Omega(n^2)$, but preprocessing dominates faster algorithms. Since most interesting functions are in $\Omega(n^2)$ (e.g. adding two numbers), one might consider the problem negligable.

-

3
Until you convince me why this is supposed to be the case, I shall keep that downvote. – Andrej Bauer Feb 15 '11 at 13:33

1
I would like to hear some evidence for your claim. All of it, it's just one claim. – Andrej Bauer Feb 15 '11 at 18:44

2
Oh, I see what you are referring to. Ok, sorry. However, the question is not about that. It's a slight variation. – Andrej Bauer Feb 16 '11 at 6:15

6
I think that the case with t=Ω(n^2) is the easy case because you can afford the time to shift the input string. The essential case is when t=o(n^2). I do not know how important it is to consider single-tape TM with o(n^2) time, but the question is about that. – Tsuyoshi Ito Feb 16 '11 at 21:38

3
The original question already implies that the case $\Omega(n^2)$ is easy; hence I do not really see how this answer adds anything new... – Jukka Suomela Feb 17 '11 at 8:26
show 4 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 59, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.902540385723114, "perplexity_flag": "middle"}