Complex Systems

Turing Machines with Two Letters and Two States Download PDF

Maurice Margenstern
Université Paul Verlaine — Metz, LITA, EA 3097
UFR MIM, Campus du Saulcy, 57045 METZ Cédex, France


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.