turing

Introduction

This program implements a deterministic Turing machine with a single tape and a single track. It provides methods to compute the Goedel number for a Turing machine as well as constructing a Turing machine from a Goedel number, supporting different encoding schemes. The main purpose of this software is to demonstrate the construction of the SELF machine, i.e., a Turing machine that outputs its own Goedel number.

Features

• deterministic single-tape single-track Turing machine implementation
• conversion to/from Goedel numbers supporting different encoding schemes
• construction of SELF machines based on the writer/transcoder concept
• examples for simple Turing machines
• examples for several SELF machines

Download

• turing-0.9.3.tar.bz2 (61 kB)
• turing-0.9.2.tar.bz2 (50 kB)
• turing-0.9.1.tar.bz2 (50 kB)
• turing-0.9.tar.bz2 (50 kB)

Bibliography

• [MG02] Margenstern, Maurice and Rogozhin, Yurii: Self-describing Turing machines, Fundamenta Informaticae 50, pp. 285 - 303, 2002
  This paper constructs very short self-describing Turing machines. In contrast to my implementation it uses alphabets of size three to represent Goedel numbers, i.e., numbers can be encoded in binary. This difference and very sophisticated encodings yield self-describing Turing machines with roughly 200 transitions.