Talk:Turing-machine
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)