This repository contains any material required to run the "Universal Turing Machine" published by Marvin Minsky in "Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice-Hall, 1967" using Martin Ugarte's "Turing Machine Simulator"
It is primarily intended for the author's lecture on the "Foundations of Computer Science" at Stuttgart University of Applied Sciences, but may also be of interest to others.
An introductory description of "Turing Machines" (TMs) in general and "Universal Turing Machines" (UTMs) in particular (with examples) can be found on the author's web site (german version, english version)
The actual UTM shown here is basically a direct port of a Python implementation by Pontus Johnson (which can be found in another Github repository)
However, in order to be run using Martin Ugarte's Turing Machine Simulator, the port had to be prefixed with a "preamble" which places the read/write head of the UTM at a position where Marvin Minsky's UTM implementation expects it to be in the beginning.
In the same way as in the original Python implementation, the port also differentiates between
- state transitions explicitly mentioned in Marvin Minsky's simplified state diagram for his UTM,
- additional (implicitly assumed) state transitions not mentioned in the diagram, but required for the UTM to operate correctly and
- additional (implicitly assumed) state transitions not mentioned in the diagram, which are not needed for the intended operation of the UTM but in fact make the UTM vulnerable to attacks (as described in Pontus Johnson's article "Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine")
This repository contains the following files
- Marvin-Minsky-UTM.txt
containing a "program" prepared for the Turing Machine Simulator, which implements Marvin Minsky's UTM and may be used to simulate other TMs - example.txt
with a trivial example illustrating the operation of an UTM - binary-counter.txt
with another example for the UTM - namely the "binary counter" which is to be "attacked", i.e., superseded by a hack that simply erases the input tape - attack.txt
with the initial contents of the UTM's tape in order to run an attack
Credits go to Martin Ugarte for his wonderful Turing Machine Simulator and to Pontus Johnson who found the mentioned vulnerability and developed a successful attack (as the author of these lines here just ported that work to the simulator)