![Complex Systems Complex Systems](https://www.complex-systems.com/wp-content/themes/complexsystems/img/ui_logo_small.png)
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.