I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, it is based on a Turing machine that doesn't halt.

If we consider only computations that do halt (that end on an additional accepting state), the set of initial configurations that produce such computations could be considered a formal language. In that case, what would be the limitation to the class of languages that could be defined by those machines (with 2 states and 3 symbols)? Could they be specified using regular expressions?

Any help is appreciated.

The following TM halts and accepts iff the initial configuration is $(d_{1}01^*[1]d_{2} + d_{3}[0]d_{4})$, where $d_{i} \in \Sigma^\infty$, and $[x]$ (with $x \in \Sigma$) denotes the position of the tape head.

enter image description here

  • 1
    $\begingroup$ There can be no such (i.e. computable) characterisation of the set of always terminating Turing machines. That would solve the Halting problem. See also here. (Duplicate?) In particular, it's definitely not the same set as those for REG since REG $\subsetneq$ CSL $\subsetneq$ R. $\endgroup$ – Raphael Jun 12 '15 at 11:41
  • $\begingroup$ You mean it can only be found out if we took them one by one, right? $\endgroup$ – André Souza Lemos Jun 12 '15 at 11:43
  • $\begingroup$ Since I don't understand what you mean by that, I don't think that I mean that. $\endgroup$ – Raphael Jun 12 '15 at 11:43
  • $\begingroup$ A characterization of the kinds of languages that can be defined by machines from this finite (and approachable) set. That's what I mean. $\endgroup$ – André Souza Lemos Jun 12 '15 at 11:51
  • $\begingroup$ What do you mean by 'approachable'? Can you enumerate them? Can you find out, given a machine, whether it is one? $\endgroup$ – reinierpost Jun 12 '15 at 12:49

Your Answer

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

Browse other questions tagged or ask your own question.