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

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

<p>and rejects every string of the form</p>

<p>$L_N = \{ r\; 0^n \; 1^m\;A \mid m &gt; n \}$</p>

<p>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.</p>

<p>Informal description:</p>

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

<p>Example:</p>

<pre><code>  :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 &gt; 1 A
   R c c &lt;:&gt; 1 A
   R c c &lt; &lt;:1 A
   R c c &lt;:&lt; &gt; A
   R c c:&lt; &gt; &gt; A
   R c:c &gt; &gt; &gt; A
   R c &lt;:&gt; &gt; &gt; A
   ...
   R c &lt; &lt; &lt; &lt;:A ACCEPT
</code></pre>

<p>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)).</p>

<p>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  $&lt;$ or $&gt;$ which cannot lead to an infinite loop).</p>

<p>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.</p>

<p>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.</p>

<p>So $L(M)$ <em>is not regular</em>.</p>

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

<p>$L = \{ 1^{2n} \}$</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-08-02T16:54:35.533Z
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) ...
David G
CC BY-SA 3.0
2017-08-02T17:30:53.507Z
@DavidG: You're right! I didn't think about it too much ... I try to fix it.
Marzio De Biasi
CC BY-SA 3.0
2017-08-02T18:56:41.603Z
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.
Mikhail Rudoy
CC BY-SA 3.0
2017-08-02T20:12:23.023Z
@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 ...
Marzio De Biasi
CC BY-SA 3.0
2017-08-02T13:08:45.267Z
2017-08-02T20:57:20.997Z
2017-08-02T20:57:20.997Z
Marzio De Biasi
<p>I underestimated the power of $C_3$ ... actually it is not too far from  <em>Hypercomputation</em>!</p>

<p>(I post this as a separate answer for better clarity)</p>

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

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

<p>and rejects strings of the form:</p>

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

<p>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) <em>bounce the head back to the right</em>, 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.</p>

<p>The transitions are:</p>

<ul>
<li>on $r$ write $R$ and move right (prepare for rejecting)</li>
<li>on $0$ write $Z$ and move right (moving toward the center, set the binary counter to 0 ..)</li>
<li>on $1$ write $&gt;$ 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)</li>
<li>on $&gt;$ write $&lt;$ and go right (right-to-left crossing of the second half of the string, prepare for next  left-to-right)</li>
<li>on $&lt;$ write $&gt;$ and go left (left-to-right crossing of the second half of the string, prepare for next  right-to-left)</li>
<li>on $Z$ write $S$ and move right (transform the digit to one and bounce back to the right towards the unary counter)</li>
<li>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)</li>
<li>on $)$ write $Z$ and move right (set the zero that will cause the bounce, and let the head move to the right)</li>
<li>on $A$ accept, on $R$ reject</li>
<li>on blank $b$ reject</li>
</ul>

<p>Example:</p>

<pre><code> :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 &gt; 1 1 1 1 1 1 1 R
  A Z Z S:&gt; 1 1 1 1 1 1 1 R
  A Z Z S &lt;:1 1 1 1 1 1 1 R
  A Z Z S:&lt; &gt; 1 1 1 1 1 1 R
  A Z Z:S &gt; &gt; 1 1 1 1 1 1 R
  A Z:Z ) &gt; &gt; 1 1 1 1 1 1 R
  A Z S:) &gt; &gt; 1 1 1 1 1 1 R
  A Z S Z:&gt; &gt; 1 1 1 1 1 1 R
  ...
  A Z S:Z &gt; &gt; &gt; 1 1 1 1 1 R
  ...
  A Z S S &lt; &lt; &lt;:1 1 1 1 1 R
  ...
  A S:) ) &gt; &gt; &gt; &gt; 1 1 1 1 R
  ...
 :A ) ) ) &gt; &gt; &gt; &gt; &gt; &gt; &gt; &gt; R ---&gt; ACCEPT
</code></pre>

<p>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 $&lt;, &gt;$ which cannot lead to an infinite loop).</p>

<p>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$).</p>

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

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

<p>But by a simple application of the <a href="https://en.wikipedia.org/wiki/Ogden%27s_lemma" rel="noreferrer">Ogden's Lemma</a> 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$).</p>

<p>So $L(M)$ <strong>is not Context Free</strong>.</p>

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

CC BY-SA 3.0
2017-08-05T14:06:38.737Z
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.)
Emil Jeřábek
CC BY-SA 3.0
2017-08-05T18:36:01.943Z
@EmilJeřábek: I said "not too far" ... don't stifle the ambitions of that tiny class ... :-)
Marzio De Biasi
CC BY-SA 3.0
2017-08-03T19:51:01.247Z
2017-08-03T19:51:01.247Z
Marzio De Biasi
<p>In this answer it is assumed that Turing machines have both-way infinite tapes. The claims do not hold for one-way infinite tapes.</p>

<p>Let me first define the class of languages $C_3'$ as the class of all languages <em>decidable</em> by one-tape Turing machines with 3 states ($C_3$ was defined as the class of languages <em>recognizable</em> 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'$).</p>

<p>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, <strong>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$.</strong> 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 <strong>if $L\in C_3$ and $1^n\in L$ for $n\geq 1$, then $1^m\in L$ for all $m\geq n$.</strong> 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'$.</p>

<hr>

<p>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:</p>

<p>1) <em>When $M$ reads 1, it accepts or rejects.</em></p>

<p>2) <em>When $M$ reads 1, it moves the head to the left.</em> 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.</p>

<p>3) <em>When $M$ reads 1, it moves the head to the right.</em> 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.</p>

<p>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.</p>

<hr>

<p>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:</p>

<p>1) <em>When $M$ reads 1, it accepts.</em></p>

<p>2) <em>When $M$ reads 1, it moves the head to the left.</em> 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$.</p>

<p>3) <em>When $M$ reads 1, it moves the head to the right.</em> 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.</p>

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

CC BY-SA 3.0
2017-08-05T16:19:33.143Z
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.)
Mikhail Rudoy
CC BY-SA 3.0
2017-08-05T18:43:44.900Z
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 \}$ ...
Marzio De Biasi
CC BY-SA 3.0
2017-08-05T19:19:22.220Z
@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).
David G
CC BY-SA 3.0
2017-08-05T19:45:10.963Z
@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.
David G
CC BY-SA 3.0
2017-08-06T01:14:01.433Z
@MikhailRudoy If we play with non-halting TMs then things are a little bit different; for example, for any $k > 0$ it's easy to build a machine $M_k$ that accepts $\{ 1^n \mid n \geq k\}$ and  runs forever on smaller inputs.
Marzio De Biasi
CC BY-SA 3.0
2017-08-06T04:19:22.760Z
@DavidG I believe the default behavior used in most formal TM definitions for what happens when a TM's head moves left from the first cell is that the head actually stays in the same place.
Mikhail Rudoy
CC BY-SA 3.0
2017-08-06T04:21:54.747Z
@MarzioDeBiasi I'm OK with allowing that. My intuition when asking the question was that building these machines to always halt is super difficult, so I don't even want to worry about decidability. That is why I made sure to use the term "recognizes" everywhere in the question rather than "decides".
Mikhail Rudoy
CC BY-SA 3.0
2017-08-06T09:22:18.220Z
@MikhailRudoy: there is some standard literature where the standard definition of the TM allows left crossings from the first cell, like Hopcroft, Motwani, Ullman: Introduction to automata theory, languages, and computation and Peter Linz: An introduction to formal languages and automata. I was used on that. Next time I must ask about the model first ... I agree that now my claims do not answer the question.
David G
CC BY-SA 3.0
2017-08-06T18:21:29.407Z
@DavidG If your answer works for some particular model (but not the one I had in mind), the answer is definitely still worthwhile and it would be great if you specified the model at the top of your answer. After all, part of my question was about the differences in behavior of the class $C_3$ as the TM model varies.
Mikhail Rudoy
CC BY-SA 3.0
2017-08-06T18:37:30.160Z
@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](http://www.sciencedirect.com/science/article/pii/S0019995869904720). 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).
Marzio De Biasi
CC BY-SA 3.0
2017-08-08T07:43:18.363Z
@MikhailRudoy As recommended, I specified in the beginning of the post that the answer only holds for TMs with both-way infinite tapes.
David G
CC BY-SA 3.0
2017-08-05T13:51:16.423Z
2017-08-08T07:41:19.493Z
2017-08-08T07:41:19.493Z
David G
<p>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).</p>

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

<ol>
<li>Has $C_3$ previously been studied? </li>
<li>Is $C_3$ known to equal any other complexity/computability classes of interest?</li>
<li>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?</li>
<li>How does $C_3$ relate to the class of regular languages, $Regular$? (In particular, is every regular language in $C_3$?)</li>
</ol>

<p>A (rather cursory) search brought up only <a href="https://cs.stackexchange.com/questions/75161/does-every-turing-machine-have-an-equivalent-single-state-n-tape-turing-machin">this cs.stackexchange post</a> which is relevant but doesn't answer my questions and <a href="https://hal.archives-ouvertes.fr/inria-00074105/document" rel="noreferrer">this paper</a>, 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.</p>

CC BY-SA 3.0
2017-08-01T19:50:29.413Z
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.
David G
CC BY-SA 3.0
2017-08-01T22:19:57.087Z
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).
Mikhail Rudoy
CC BY-SA 3.0
2017-08-02T16:47:10.757Z
You are right, my intuition was wrong.
David G
<automata-theory><turing-machines><cellular-automata>
Class of languages recognizable by single-tape 3-state TMs
Mikhail Rudoy
# Class of languages recognizable by single-tape 3-state TMs

(Asked by: username_0 on 2017-08-01)

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](https://cs.stackexchange.com/questions/75161/does-every-turing-machine-have-an-equivalent-single-state-n-tape-turing-machin) which is relevant but doesn't answer my questions and [this paper](https://hal.archives-ouvertes.fr/inria-00074105/document), 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.

**Tags:** automata-theory, turing-machines, cellular-automata
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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).  
> **username_1**: You are right, my intuition was wrong.  

---

## 3 answers

### Answer by username_2 on 2017-08-02. Score: 7

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.

> **Comments:**
> **username_1**: 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) ...  
> **username_2**: @DavidG: You're right! I didn't think about it too much ... I try to fix it.  
> **username_0**: 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.  
> **username_2**: @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 ...  

---

### Answer by username_2 on 2017-08-03. Score: 5

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.

> **Comments:**
> **username_3**: 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.)  
> **username_2**: @EmilJeřábek: I said "not too far" ... don't stifle the ambitions of that tiny class ... :-)  

---

### Answer by username_1 on 2017-08-05. Score: 2

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\}$.

> **Comments:**
> **username_0**: 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.)  
> **username_2**: 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 \}$ ...  
> **username_1**: @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).  
> **username_1**: @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.  
> **username_2**: @MikhailRudoy If we play with non-halting TMs then things are a little bit different; for example, for any $k > 0$ it's easy to build a machine $M_k$ that accepts $\{ 1^n \mid n \geq k\}$ and  runs forever on smaller inputs.  
> **username_0**: @DavidG I believe the default behavior used in most formal TM definitions for what happens when a TM's head moves left from the first cell is that the head actually stays in the same place.  
> **username_0**: @MarzioDeBiasi I'm OK with allowing that. My intuition when asking the question was that building these machines to always halt is super difficult, so I don't even want to worry about decidability. That is why I made sure to use the term "recognizes" everywhere in the question rather than "decides".  
> **username_1**: @MikhailRudoy: there is some standard literature where the standard definition of the TM allows left crossings from the first cell, like Hopcroft, Motwani, Ullman: Introduction to automata theory, languages, and computation and Peter Linz: An introduction to formal languages and automata. I was used on that. Next time I must ask about the model first ... I agree that now my claims do not answer the question.  
> **username_0**: @DavidG If your answer works for some particular model (but not the one I had in mind), the answer is definitely still worthwhile and it would be great if you specified the model at the top of your answer. After all, part of my question was about the differences in behavior of the class $C_3$ as the TM model varies.  
> **username_2**: @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](http://www.sciencedirect.com/science/article/pii/S0019995869904720). 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).  
> **username_1**: @MikhailRudoy As recommended, I specified in the beginning of the post that the answer only holds for TMs with both-way infinite tapes.  

---

