Turing Machines for Real (TM4R)

Michael PÉRIN, Verimag / Univ. Grenoble-Alpes

Projet 2019 : Réalisation d'une version 3 bandes de la Machine de Turing Universelle (sujet)

The TM4R project aims at developping the Turing Machine constructions

Those constructions have been described in books but never implemented:

• Emulation of a TM operating on an n-symbols alphabet by a TM operating on binary alphabet (2017)
• The Universal Turing Machine (2019)
• Emulation of a n-Bands TM by a single-band TM (2021 ?)
• The Universal Scheduler running two Turing Machines one step each (2023 ?)

Modules already available

• Constructions for defining Turing Machines
• An execution engine with an html output
• An execution layer on top of the previous one for emulation of on-the-fly transformations
• An output of the control flow graph of a Turing_Machine in a .dot for the free graph vizualizer software (graphviz)

Examples of Turing Machines

• Some examples of single-band Turing Machines
• The known busy beavers
• Some examples of two-bands Turing Machines

Available engine outputs

demo/run/ contains html files

• The run of the 4-states Busy Beaver (107 steps)
• The run of a TM which erases the content of a vector while keeping the structure (..,..)
• The run of its binary version operating on the 2-symbols alphabet {T,F}
• The run of a 2-bands Turing Machine performing the xor of two bands

demo/dot/ contains some control flow graphs in .dot format

• The 4-states Busy Beaver
• The xor 2-bands Turing Machine
• The erase-vec 1-band Turing Machine