From Esolang
Jump to navigation Jump to search

Computational class

According to T. Neary and D. Woods, it was shown by L. Pavlotskaya that the halting problem is decidable for all Turing machines with 3 states and 2 symbols, where one transition is reserved for halting, which matches exactly the Turing-machine restrictions. Int-e (talk) 12:11, 6 August 2018 (UTC)