9
$\begingroup$

I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note that I allow arbitrary (finite) tape alphabets (i.e., the tape alphabet is not restricted to equal the input alphabet).

For convenience, call the class of languages recognizable by such TMs $C_3$. I have several questions about this class:

  1. Has $C_3$ previously been studied?
  2. Is $C_3$ known to equal any other complexity/computability classes of interest?
  3. Is the class $C_3$ robust to changes in model. For example, if the TMs used are allowed to stay in place during a single transition (as opposed to always moving either left or right) or if the tape is made to be infinite in both directions instead of just to the right, does the class of languages recognizable by 3-state 1-tape TMs change?
  4. How does $C_3$ relate to the class of regular languages, $Regular$? (In particular, is every regular language in $C_3$?)

A (rather cursory) search brought up only this cs.stackexchange post which is relevant but doesn't answer my questions and this paper, which I haven't read in enough detail to be sure that it concerns exactly the class $C_3$ rather than a similar but different class (the paper claims to prove that (1) every language in $C_3$ is decidable and (2) that $C_3$ and $Regular$ are distinct classes with non-empty intersection). As pointed out in the comments of the cs.stackexchange post, these kinds of TMs can be thought of as very particular cellular automata, so maybe someone who knows the literature on cellular automaton theory could help.

$\endgroup$
  • 1
    $\begingroup$ If you have only one non-terminating state and one tape (input tape), then your machine cannot remember anything that it read. So, it can accept or reject exactly inputs that contain definite symbol(s) from the input alphabet. $\endgroup$ – David G Aug 1 '17 at 19:50
  • 4
    $\begingroup$ The machine can't remember what it read, but it can rewrite what it read with something else. So I don't really see why the characterization you give would be correct. (i.e. I can think of a simple machine which accepts $01$ and rejects $011$; here the behavior is not determined entirely by which symbols are in the input). $\endgroup$ – Mikhail Rudoy Aug 1 '17 at 22:19
  • 1
    $\begingroup$ You are right, my intuition was wrong. $\endgroup$ – David G Aug 2 '17 at 16:47
7
$\begingroup$

The beast is extremely powerful, for example we can build a TM $M$ that accepts every string of the form

$L_Y = \{ r\; 0^n \; 1^m\;A \mid m \leq n \}$

and rejects every string of the form

$L_N = \{ r\; 0^n \; 1^m\;A \mid m > n \}$

The idea is to transform the first $r$ into $R$ and then let the head reach the middle of the string then do a "stateless" zig-zag; if it reaches $A$ before $R$ then it accepts.

Informal description:

  • on $r$ write $R$ and move right (prepare for rejecting)
  • on $0$ write $c$ and move right (moving toward the center)
  • on $1$ write $>$ and move left (mark a $1$, prepare for next left-to-right crossing, and go left)
  • on $c$ write $<$ and move right (mark a $0$, prepare for the next right-to-left crossing, and go right)
  • on $<$ write $>$ and go left (left-to-right crossing, prepare for next right-to-left)
  • on $>$ write $<$ and go right (right-to-left crossing, prepare for next left-to-right)
  • on $A$ accept, on $R$ reject
  • on blank $b$ reject

Example:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

This zig-zag technique is used in the smallest 2-states Universal Turing machine (it has 18 symbols) constructed by Rogozhin (Rogozhin 1996. TCS, 168(2):215–240)).

Some attention should be paid in order to prove that $M$ halts on all inputs (just note that it rejects on blank input and all non-halting symbols "converge" to $<$ or $>$ which cannot lead to an infinite loop).

As commented by DavidG, the language $L(M)$ recognized by $M$ is a superset of $L_Y$ (i.e. $L_Y \subset L(M)$) but it doesn't contain any string from $L_N$ (i.e. $L(M) \cap L_N = \emptyset$) and - as commented by MikhailRudoy - this is enough to prove that $L(M)$ is not regular.

Indeed if $L(M)$ is regular then also $L(M) \cap \{ r0^*1^*A \} = L_Y = \{ r0^n 1^mA \mid m \leq n \}$ would be regular (which is not by a simple application of the pumping lemma); leading to a contradiction.

So $L(M)$ is not regular.

... But like all superheroes $C_3$ has an Achille's heel: it cannot even recognize the regular:

$L = \{ 1^{2n} \}$

Informally it can use only the leftmost $b 1 ...$ ($b$ is the blank symbol) or the rightmist $1b...$ as a hook and "expand" in the other direction; but the final Accept or Reject cannot be on the blank symbol of the opposite side, so it can be done only on the inner part of the $1$s and starting from a long enough input it can be "faked" stretching it by one.

Finally - after reading the paper - I can confirm that the one-state TM described in it matches your $C_3$ class ... (so nothing new here :-) ...and the langauge used by the author to prove that it contains non-regular languages is very similar to mine.

$\endgroup$
  • 1
    $\begingroup$ I very much like the answer (+1). However, the TM that is described accepts a different language. It, for example, accepts also strings rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (after A it could be anything instead of ones) ... $\endgroup$ – David G Aug 2 '17 at 16:54
  • $\begingroup$ @DavidG: You're right! I didn't think about it too much ... I try to fix it. $\endgroup$ – Marzio De Biasi Aug 2 '17 at 17:30
  • 4
    $\begingroup$ Actually, even through $L$ is not the language recognized by the described TM, that language is definitely not regular: if that TM is $M$, then $L(M) \cap r0^*1^*A = L$ so a short proof by contradiction (if $L(M)$ is regular then $L(M) \cap r0^*1^*A = L$ will also be regular; contradiction) can show that $L(M)$ is not regular. $\endgroup$ – Mikhail Rudoy Aug 2 '17 at 18:56
  • 3
    $\begingroup$ @MikhailRudoy: yes! I had the same idea. I opened cstheory to edit the answer, and saw your comment. Let's see if I can rewrite the answer taking into account your comment ... $\endgroup$ – Marzio De Biasi Aug 2 '17 at 20:12
5
$\begingroup$

I underestimated the power of $C_3$ ... actually it is not too far from Hypercomputation!

(I post this as a separate answer for better clarity)

We can build a single state Turing machine $M$ that accepts the strings of the form:

$L_Y = \{ a \; 0^n \; 1^m \; R \mid m \geq 2^n\}$

and rejects strings of the form:

$L_N = \{ a \; 0^n \; 1^m \; R \mid m \lt 2^n\}$

The idea and construction is similar to the one in the previous answer: transform the first $a$ into $A$, let the head reach the middle of the string then do a "stateless" zig-zag, but the transitions "implement"a "binary counter" on the first half in this way: on $Z$ (Zero) bounce the head back to the right, and convert the $Z$ into a $S$ (One) the next time the head reaches the $S$, transform it to a $)$ and let the head move left; when the head reaches the $)$ transform it to a $Z$. The second half of the string behaves like a unary counter.

The transitions are:

  • on $r$ write $R$ and move right (prepare for rejecting)
  • on $0$ write $Z$ and move right (moving toward the center, set the binary counter to 0 ..)
  • on $1$ write $>$ and move left (mark a $1$ and decrement the unary counter, prepare for next left-to-right crossing, and bounce back to the binary counter)
  • on $>$ write $<$ and go right (right-to-left crossing of the second half of the string, prepare for next left-to-right)
  • on $<$ write $>$ and go left (left-to-right crossing of the second half of the string, prepare for next right-to-left)
  • on $Z$ write $S$ and move right (transform the digit to one and bounce back to the right towards the unary counter)
  • on $S$ write $)$ and move left (clear the digit, and let the head move to the left like a "carry", prepare for the next left-to-right of the first part)
  • on $)$ write $Z$ and move right (set the zero that will cause the bounce, and let the head move to the right)
  • on $A$ accept, on $R$ reject
  • on blank $b$ reject

Example:

 :a 0 0 0 1 1 1 1 1 1 1 1 R
  A:0 0 0 1 1 1 1 1 1 1 1 R
  A Z:0 0 1 1 1 1 1 1 1 1 R
  ...
  A Z Z Z:1 1 1 1 1 1 1 1 R
  A Z Z:Z > 1 1 1 1 1 1 1 R
  A Z Z S:> 1 1 1 1 1 1 1 R
  A Z Z S <:1 1 1 1 1 1 1 R
  A Z Z S:< > 1 1 1 1 1 1 R
  A Z Z:S > > 1 1 1 1 1 1 R
  A Z:Z ) > > 1 1 1 1 1 1 R
  A Z S:) > > 1 1 1 1 1 1 R
  A Z S Z:> > 1 1 1 1 1 1 R
  ...
  A Z S:Z > > > 1 1 1 1 1 R
  ...
  A Z S S < < <:1 1 1 1 1 R
  ...
  A S:) ) > > > > 1 1 1 1 R
  ...
 :A ) ) ) > > > > > > > > R ---> ACCEPT

Some attention should be paid in order to prove that $M$ halts on all inputs (just note that it rejects on blank input and all non-halting symbols "cycle" through $( , S , Z$ or $<, >$ which cannot lead to an infinite loop).

The language $L(M)$ is a superset of $L_Y$ ($L_Y \subset L(M)$) and it doesn't contain strings from $L_N$ ($L(M) \cap L_N = \emptyset$).

Suppose that $L(M)$ is Context Free, then - by closure properties of CFLs, intersecting it with the regular language $\{r 0^* 1^* A\}$ produce a CF language:

$L(M) \cap \{r 0^* 1^* A\} = \{ a \; 0^n \; 1^m \; R \mid m \geq 2^n\} = L_Y$

But by a simple application of the Ogden's Lemma for CFL we can prove that $L_Y \notin CFL$: just pick a long enough $s \in L_Y$ and mark all the $0$s; at least one zero can be pumped and whatever is the number of $1s$ in the pumping string the exponential growth of $2^n$ leads to a string $\notin L_Y$).

So $L(M)$ is not Context Free.

... now I'm wondering if this is another "reinventing the wheel" answer, or it is a new (small) result.

$\endgroup$
  • $\begingroup$ Well, the language here is computable in as low a class as coNLOGTIME, so it does not exactly require hypercomputation. (In fact, $L_Y$ and $L_N$ can be separated even in DLOGTIME.) $\endgroup$ – Emil Jeřábek supports Monica Aug 5 '17 at 14:06
  • $\begingroup$ @EmilJeřábek: I said "not too far" ... don't stifle the ambitions of that tiny class ... :-) $\endgroup$ – Marzio De Biasi Aug 5 '17 at 18:36
2
$\begingroup$

In this answer it is assumed that Turing machines have both-way infinite tapes. The claims do not hold for one-way infinite tapes.

Let me first define the class of languages $C_3'$ as the class of all languages decidable by one-tape Turing machines with 3 states ($C_3$ was defined as the class of languages recognizable by one-tape Turing machines with 3 states). I introduced the class $C_3'$ because in my original answer, I unconsciously swaped the classes $C_3$ and $C_3'$ (I only considered the class $C_3'$).

This answer is more a complement to @MarzioDeBiasi answers. He showed that the classes $C_3$ and $C_3'$ are not contained in CFL and thus contain quite interesting languages. However, as I will show in this post, each language $L$ in $C_3'$ has the property that the set $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$ is either in $L$ or in its complement $L^C$. Thus $C_3'$ is also very restrictive, eg. it contains only trivial unary languages $\{\}$, $\{\varepsilon\}$, $\{1^n;n\in\mathbb{N}\}$ and $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$. The class $C_3$ contains a bit more unary languages. However, it holds that if $L\in C_3$ and $1^n\in L$ for $n\geq 1$, then $1^m\in L$ for all $m\geq n$. A simple corollary is that not all regular languages are in $C_3$ nor in $C_3'$. Also the language $\{1\}$ is not in $C_3$ nor in $C_3'$.


For the claim (in bold) about $C_3'$, it is enough to prove that a one-tape Turing machine $M$ with 3 states that always halts either accepts or rejects all strings from $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$. Suppose that a string of the form $1^n$, $n\in\mathbb{N}\backslash\{0\}$, is given to $M$. There are three cases:

1) When $M$ reads 1, it accepts or rejects.

2) When $M$ reads 1, it moves the head to the left. If we want $M$ to halt on this input, it must accept, reject or move to the right on the blank symbol. Hence, it never visits the cell to the right of the initial cell of the tape. If it would, it would run forever on input 1.

3) When $M$ reads 1, it moves the head to the right. It follows that after $n$ steps, the content of the tape is $A^n$ where $A$ is some symbol from the tape alphabet and the head of $M$ is on the leftmost blank symbol to the right of the last $A$. If we want $M$ to halt on this input, it must accept, reject or move to the left on the blank symbol. As in case 2), the head of $M$ will now never visit the cell directly to the left of the rightmost $A$. If it would, then $M$ would run forever on input 1.

It is clear that in all three cases $M$ accepts all strings from the set $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$ or it rejects them all.


The proof of the claim (in bold) about $C_3$ follows the same line as above. We take a one-tape 3-state Turing machine $M$ that accepts a string $1^n$ for some $n\geq 1$. Suppose $M$ is given an input $1^m$ for $m\geq n$. We have to prove that $M$ accepts this input. We have 3 cases:

1) When $M$ reads 1, it accepts.

2) When $M$ reads 1, it moves the head to the left. Because $M$ accepts the input $1^n$, it has to accept or move to the right on the blank symbol. Hence, it never visits the $n$th cell to the right of the initial cell. If it would, it would run forever on input $1^n$.

3) When $M$ reads 1, it moves the head to the right. It follows that after $m$ steps, the content of the tape is $A^m$ where $A$ is some symbol from the tape alphabet and the head of $M$ is on the leftmost blank symbol to the right of the last $A$. Because $M$ accepts the input $1^n$, it must accept or move to the left on the blank symbol. As in case 2), the head of $M$ will now never visit the $n$th cell to the left of the rightmost $A$. This is because on the input $1^n$, $M$ does not visit the cell directly left of the initial cell, because it contains the blank symbol and if it would read it, it would run forever.

It is clear that in all three cases $M$ accepts all strings from the set $\{1^m;m\geq n\}$.

$\endgroup$
  • $\begingroup$ First of all, nowhere in the question does it say that M must halt on all inputs, so that screws up some of the logic in this answer. Beyond that, the logic in several of the cases doesn't make sense to me. For example, in case 3, if M moves left on both blank and A, then M will visit the cell directly left of the rightmost A (in direct contrast to the claim from the answer.) $\endgroup$ – Mikhail Rudoy Aug 5 '17 at 16:19
  • $\begingroup$ Nice; another way to state it is: if $\Sigma = \{1\}$ (unary languages) then $\exists k \mbox{ s.t. }1^k \in L(M) \Leftrightarrow L(M) = \{1^n \mid n > 0 \}$ ... $\endgroup$ – Marzio De Biasi Aug 5 '17 at 18:43
  • $\begingroup$ @MikhailRudoy, to first clarify the case 3: if the head moves left on both A and blank symbol, then it will move left forever and will not halt. If it ever (say after 100 steps) visits the cell directly left of the rightmost A, then in the case of input 1 it never halts (in this case the cell directly left of the rightmost A will contain the blank symbol). $\endgroup$ – David G Aug 5 '17 at 19:19
  • $\begingroup$ @MikhailRudoy, it is true that I assumed that a Turing machine has to halt. I will edit the answer to include also the possibility that it runs forever. The result is similar. $\endgroup$ – David G Aug 5 '17 at 19:45
  • 3
    $\begingroup$ @MikhailRudoy: BTW the hatling problem is decidable for 1 state Turing machines; see Gabor T. Herman, The uniform halting problem for generalized one-state turing machines. The model described there is a little bit different from yours: the TM accepts if it ends in a mortal configuration (there is no Accept/Reject); but the result also applies to your model (just Halt the TM on the symbols that lead to your extra Accept/Reject states). $\endgroup$ – Marzio De Biasi Aug 6 '17 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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