<p>The Turing machine (TM) is a fundamental mathematical model in the field of algorithmic processes. To our knowledge, the printing of a TM program by itself (starting with the blank tape) has not been practically realized yet, despite the fact that the reproduction of the program describing the driving algorithm is a key step in self-replication. Although, there exist so-called self-describing algorithms/machines, they print not their (complete) program itself, only some (abbreviated) representation of it. Our present work is to contribute to fill this gap by means of constructing the program of a new kind of TMs, that we call self-printing TMs. While printing their own program (starting with the blank tape), the possibility of printing any (other) TM program is built in the proposed self-printing (or quine) TMs. This kind of universality is utilized to improve von Neumann’s fundamental self-replicating system, in the sense that the improved system requires less working components. As a practical contribution, a particular self-printing TM program, with 146,852 functional instructions, is provided. By running this program, one can directly check its self-printing ability. Apart from the theoretical and mathematical respects on self-replication, the proposed self-printing TM may serve as a tool for studying fundamental life-like phenomena (like mutation and evolution) in their pure (most direct) form, in the field of artificial and biological life.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Construction of a self-printing (quine) Turing machine program with the possibility of printing any other program

  • Richárd Kicsiny,
  • Zoltán Varga

摘要

The Turing machine (TM) is a fundamental mathematical model in the field of algorithmic processes. To our knowledge, the printing of a TM program by itself (starting with the blank tape) has not been practically realized yet, despite the fact that the reproduction of the program describing the driving algorithm is a key step in self-replication. Although, there exist so-called self-describing algorithms/machines, they print not their (complete) program itself, only some (abbreviated) representation of it. Our present work is to contribute to fill this gap by means of constructing the program of a new kind of TMs, that we call self-printing TMs. While printing their own program (starting with the blank tape), the possibility of printing any (other) TM program is built in the proposed self-printing (or quine) TMs. This kind of universality is utilized to improve von Neumann’s fundamental self-replicating system, in the sense that the improved system requires less working components. As a practical contribution, a particular self-printing TM program, with 146,852 functional instructions, is provided. By running this program, one can directly check its self-printing ability. Apart from the theoretical and mathematical respects on self-replication, the proposed self-printing TM may serve as a tool for studying fundamental life-like phenomena (like mutation and evolution) in their pure (most direct) form, in the field of artificial and biological life.