Recursion Theorems and Self-Replication Via Text Register Machine Programs.
Lawrence S. Moss · Bulletin of the European Association for Theoretical Computer Science · 2006
Register machine programs provide explicit proofs of the sn -Theorem, Kleene’s Second Recursion Theorem, and Smullyan’s Double Recursion Theorem. Thus these programs provide a pedagogically useful approach. We develop this topic from scratch, hence without appeal to the existence of universal programs, pairing, quotation, or any form of coding device. None of the results are new from the point of view of computability theory apart from the particular formulations themselves. We introduce the notion of a text register machine; this is a register machine whose registers contain words from some alphabet and whose instructions are again words from the same alphabet. We work with a particular instruction set whose language of programs we call 1#. Tools for writing and evaluating 1# programs have been made freely available: see www.indiana.edu/∼iulg/trm. It is generally recognized that the greatest advances in modern computers came through the notion that programs could be kept in the same memory with ‘data,’ and that programs could operate on other programs, or on themselves, as though they were data.” Marvin Minsky [5]