Accelerated simulator: Difference between revisions
mNo edit summary |
updated text about Quick_Sim |
||
| (One intermediate revision by one other user not shown) | |||
| Line 7: | Line 7: | ||
=== Quick_Sim === | === Quick_Sim === | ||
[https://github.com/sligocki/busy-beaver/blob/main/Code/Quick_Sim.py Quick_Sim.py] is a python [[Inductive Proof System]] which is able to simulate some TMs up to | [https://github.com/sligocki/busy-beaver/blob/main/Code/Quick_Sim.py Quick_Sim.py] is a python [[Inductive Proof System]] which is able to simulate some TMs up to ackermannian runtime. It was written by Shawn and Terry Ligocki starting in 2005. It uses fixed-block size Macro Machines, tape compression, [[Shift rule|shift rules]], inductive rule prover and a nested exponential integer datatype. Jason Yuen (@-d) is in the process of creating a C++ version, [https://github.com/int-y1/busy-beaver-cpp quick_sim.cpp] in 2025. It is currently able to prove L1 Inductive Rules (aka Diff_Rules). | ||
=== hashlife === | === hashlife === | ||
@Mateon1 designed an accelerated simulator [https://gist.github.com/mateon1/6cdad07e15f6acf992b79dc2baf0492c fasttm.py] in 2022 based upon the [[wikipedia:Hashlife|Hashlife]] Game of Life accelerated simulator. It effectively simulates a hierarchical cached Macro Machine. | @Mateon1 designed an accelerated simulator [https://gist.github.com/mateon1/6cdad07e15f6acf992b79dc2baf0492c fasttm.py] in 2022 based upon the [[wikipedia:Hashlife|Hashlife]] Game of Life accelerated simulator. It effectively simulates a hierarchical cached Macro Machine. ([https://discord.com/channels/960643023006490684/960643023530762341/1018192129270484992 Discord Message]) | ||
[[Category:Analysis Techniques]] | [[Category:Analysis Techniques]] | ||
Latest revision as of 13:07, 19 November 2026
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 ackermannian runtime. 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)