We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
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)