RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.6, n.1 (16), 1998/

Some small self-describing Turing machines

Authors: M. Margenstern, Rogojin Iurie

Abstract

Several small self-describing Turing machines are constructed. The number of instructions varies from 275 to 206, depending on the chosen encoding principles. The previous Thatcher's result (2532 instructions of self-describing machine in Wang's format) is essentially improved.

Maurice Margenstern, Yurii Rogozhin,
Prof. Maurice Margenstern
Universitи de Metz, I.U.T. de Metz,
Dиpartement d'Informatique,
Оle du Saulcy, 57045 Metz Cedex, FRANCE
e-mail:
Dr. Yurii Rogozhin
Institute of mathematics,
Academy of Sciences of Moldova,
5 Academiei str., Kishinev,
MD-2028, Moldova
email:

Fulltext

Adobe PDF document0.18 Mb