Class of languages recognizable by single-tape 3-state TMs 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:


Has $C_3$ previously been studied? 
Is $C_3$ known to equal any other complexity/computability classes of interest?
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?
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.
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 &gt; 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 $&gt;$ and move left (mark a $1$, prepare for next left-to-right crossing, and go left)
on $c$ write $&lt;$ and move right (mark a $0$, prepare for the next right-to-left crossing, and go right)
on $&lt;$ write $&gt;$ and go left (left-to-right crossing, prepare for next  right-to-left)
on $&gt;$ write $&lt;$ 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 &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


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  $&lt;$ or $&gt;$ 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.