An empirical investigation of computational complexity theory through systematic enumeration of small Turing machines. By exhaustively analyzing machines with 1-3 states and 2-3 colors, the research establishes concrete lower bounds on computation difficulty for specific functions, discovers functions that cannot be computed faster within given machine sizes, and provides evidence of computational irreducibility. The work demonstrates that even tiny programs exhibit rich complexity, identifies specific functions requiring exponential time, and shows how different-sized machines can compute the same functions at vastly different speeds—offering tangible insights into the P vs. NP question through ruliological methodology.
Table of contents
Empirical Theoretical Computer ScienceThe Basic SetupThe s = 1, k = 2 Turing Machiness = 2, k = 2 Turing MachinesRuntimes in s = 2, k = 2 MachinesRuntime DistributionsHow Fast Can Functions Be Computed?Computing the Same Functions at Different SpeedsAbsolute Lower Bounds and the Efficiency of MachinesSpace ComplexityRuntime Distributions for Particular Inputs across Machiness = 3, k = 2 Turing Machines and the Problem of UndecidabilityMachine 600720Runtimes in s = 3, k = 2 Turing MachinesFunctions and Their Runtimes in s = 3, k = 2 Turing MachinesCan Bigger Machines Compute Functions Faster?With a Sufficiently Large Turing Machine…Beyond Binary Turing MachinesRecognizable FunctionsEmpirical Computational IrreducibilityNondeterministic (Multiway) Turing MachinesMultiway (Nondeterministic) s = 1, k = 2 Turing MachinesNondeterministic vs. Deterministic MachinesThe Limit of Nondeterminism and the RuliadWhat Does It All Mean for P vs. NP?Some Personal NotesThanksSort: