Accelerated simulator

An Accelerated Simulator is a program which simulates a Turing machine in a way that scales faster than direct, step-by-step simulation. A common method for accelerated simulation is using Inductive Proofs. But there are other methods as well, including Macro Machines and hashlife.

There are various code repositories containing tools, including accelerated simulators, that have been written over time.

Specific Simulators

Quick_Sim

Quick_Sim.py is a python Inductive Proof System which is able to simulate some TMs up to tetrational runtime (L3 Inductive Rules). It was written by Shawn and Terry Ligocki starting in 2005. It uses fixed-block size Macro Machines, tape compression, shift rules, inductive rule prover and a nested exponential integer datatype. Jason Yuen (@-d) is in the process of creating a C++ version, quick_sim.cpp in 2025. It is currently able to prove L1 Inductive Rules (aka Diff_Rules).

hashlife

@Mateon1 designed an accelerated simulator fasttm.py in 2022 based upon the Hashlife Game of Life accelerated simulator. It effectively simulates a hierarchical cached Macro Machine. (Discord Message)