Self-describing Turing machines

Article type: Research Article

Authors: Margenstern, Maurice | Rogozhin, Yurii

Affiliations: Université de Metz, I.U.T. de Metz, LITA, EA 3097, Île du Saulcy, 57045 Metz Cedex, France | Institute of Mathematics and Computer Science of the Academy of Sciences of Moldova, 5 Academiei str., Kishinev MD-2028, Moldova

Abstract: After a sketchy historical account on the question of self-describeness and self-reproduction, and after discussing the definition of suitable encodings for self-describeness, we give the construction of several self-describing Turing machines, namely self-describing machines with, respectively, 350, 267, 224 and 206 instructions.

Keywords:

Journal: Fundamenta Informaticae, vol. 50, no. 3-4, pp. 285-303, 2002