Re:P vs. NP and the Difficulty of Computation: A ruliologica...
by graemefawcett on Friday January 30, 2026 @08:04PM
(#46832190)
By fixing a tiny machine class (say s=2,3; k=2) and exhaustively asking “what’s the fastest way any machine of this size can compute this function?”, Wolfram is effectively mapping absolute speed limits within a constrained computational universe. That’s not solving P vs NP, but it is answering a nearby, clean question: given a bounded program-size budget, what time-complexity phases actually occur, and which functions are forced into each phase?
You can also read these experiments as a kind of “finite TTL” study. Bound the algorithmic information content of the machine (number of states / rule bits), and measure how many steps (hops) you inevitably have to spend to transform input into output. Some functions admit linear-time realizations under that budget; some only quadratic; some only exponential. Even in these toy universes, there are intrinsic routing costs that no cleverness can remove without increasing the size of the machine.
That feels very much in the ruliological spirit: instead of arguing in the abstract about “hardness” in an infinite model, you enumerate a small slice of the Ruliad and see which notions of difficulty survive contact with explicit programs. Whether or not this ever touches the global P vs NP question, it gives a detailed picture of how computational irreducibility and speed limits show up in actually existing rule spaces, not just in asymptotic folklore.
You can also read these experiments as a kind of “finite TTL” study. Bound the algorithmic information content of the machine (number of states / rule bits), and measure how many steps (hops) you inevitably have to spend to transform input into output. Some functions admit linear-time realizations under that budget; some only quadratic; some only exponential. Even in these toy universes, there are intrinsic routing costs that no cleverness can remove without increasing the size of the machine.
That feels very much in the ruliological spirit: instead of arguing in the abstract about “hardness” in an infinite model, you enumerate a small slice of the Ruliad and see which notions of difficulty survive contact with explicit programs. Whether or not this ever touches the global P vs NP question, it gives a detailed picture of how computational irreducibility and speed limits show up in actually existing rule spaces, not just in asymptotic folklore.