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
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: