TMC #0001: Turing Machine Simulator

A complete implementation of the theoretical model from Alan Turing's 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem."

The simulator models the 7-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ exactly. The transition function $\delta$ is encoded as a Python dictionary; the tape is a dynamic list that extends in both directions on demand.

What's included

• TuringMachine class: the core model with run(), accepts(), and print_transition_table() methods
• Parity checker: decides whether input contains an even number of 1s (2 states)
• Palindrome checker: decides whether a binary string is a palindrome (8 states)
• Unary adder: computes $m + n$ in unary representation
• UTM encoding: demonstrates encoding a TM as JSON and reconstructing it, illustrating the stored-program principle
• Halting problem explainer: prints the diagonalisation proof structure

Running

python turing_machine.py

No dependencies beyond the Python standard library.