Turing Machines with Two Letters and Two States
Maurice Margenstern
Université Paul Verlaine — Metz, LITA, EA 3097
UFR MIM, Campus du Saulcy, 57045 METZ Cédex, France
margens@univ-metz.fr
Abstract
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.
