Turing Machines with Two Letters and Two States
Université Paul Verlaine, Maurice Margenstern · Complex Systems · 2010
In this paper we provide a survey of the technique that allows giving a simple proof that all Turing machines with two letters and two states have a decidable halting problem. The result was proved by L. Pavlotskaya in 1973.