Overview
Have you ever wondered if Python is Turing complete? Well now you don’t have to!
This project is a fun recreation of the classic Turing Machine. A Turing Machine is a hypothetical computing machine which consists of the bare minimum components required for computation and can be used to solve any computable problem. This machine has three simple components:
- Tape: an infinitely long tape made of cells used for runtime memory, input, and output.
- Head: A head which can read from, write to, and traverse the cells of the tape.
- Program: A set of instructions that determine what actions should be taken on a cell’s contents depending on the program state.
The project implements a virtual Turing Machine with these components and support for custom programs and inputs. Since no personal project is complete without visuals, the Turing Machine has a live ASCII animation while running.
Technical Details
Programs
The Turing Machine accepts any properly formatted program via a text file. Instruction components are space separated, and support wildcards. * matches any symbol or indicates no action, _ matches a blank cell.
Syntax
| State | Read | Write | Move | State |
|---|---|---|---|---|
| current state | cell input | cell output | movement direction | new state |
Programs for Turing Machines are written as state machines following this cycle:
read cell > write cell > update state > move tape > repeat
The project is packaged with some example programs, courtesy of this wonderful implementation written for the web.
CLI
The program has various flags for toggling animation, setting animation speed, and preloading tapes / programs. If no tape or program input is provided on the commandline, the user is prompted for it via a menu.
While running the machine will display cycle counts and the current state, if an runtime error is encountered the program halts and associated information is displayed to the user.