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.
Class of languages recognizable by single-tape 3-state TMs
automata theory;turing machines;cellular automata