> It’s physically impossible to write down all the digits of 2^^6 — a liability of living in such a small universe.<p>What a coincidence! Just today I learned that someone found a 49 bit program whose output far exceeds Graham's number [1], and the number 2^^6 features very prominently in it.<p>[1] <a href="https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/263884#263884" rel="nofollow noreferrer">https://codegolf.stackexchange.com/questions/6430/shortest-t...</a>
So given a start state and a library of valid transitions, it's easy to create a (target, path, destination) tuple that's valid (if you don't care what the destination is). It's easy to check if a (target, path, destination) tuple is valid. It's just really hard to find the path given just the target and the destination.<p>This sounds like it has properties in common with "multiply two very large primes to create a very large composite number". Could any of this math be used as the basis for a cryptosystem?
The concept of reachability is pretty interesting in general as well.<p>"Can a spaceship with a certain delta-v reach another planet within an n-body system? (And if so, what is the fastest-to target/most resource preserving acceleration schedule?)" - apparently necessitates brute force, practically not computable on long time scales due to the chaos inherent in n-body systems (<a href="https://space.stackexchange.com/questions/64392/escaping-earth-how-could-one-attempt-to-find-the-best-solution-to-this-traject" rel="nofollow noreferrer">https://space.stackexchange.com/questions/64392/escaping-ear...</a>, <a href="https://en.wikipedia.org/wiki/N-body_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/N-body_problem</a>)<p>"Can a math proof be reached (within a certain number of proof steps) from the axioms?" - equivalent to the halting problem in most practical systems (<a href="https://math.stackexchange.com/questions/3477810/estimating-meta-mathematical-properties-of-conjectures" rel="nofollow noreferrer">https://math.stackexchange.com/questions/3477810/estimating-...</a>)<p>"Can a demoscene program with a very limited program size visualize (or codegolf program output) something specific?" - asking for nontrivial properties like this usually requires actually running each program, and there are unfathomably many short programs (<a href="https://www.dwitter.net/" rel="nofollow noreferrer">https://www.dwitter.net/</a> is a good example of this)<p>"In cookie-clicker games, is it possible to go above a certain score within a certain number of game ticks using some sequence of actions?" - in all but the simplest and shortest games (like <a href="https://qewasd.com" rel="nofollow noreferrer">https://qewasd.com</a>), this is at least not <i>efficiently</i> (optimally) solvable using MILP and the like, as the number of possible action sequences increases exponentially<p>And yet, despite these being really hard (or in the general case, impossible) problems, humans use some heuristics to achieve progress
My eyes glazed over midway through the article. I'd like them to not try explaining the problem but just out and say what the problem is, then try to explain the details so that I can pick at the pieces I don't get well enough.<p>I THINK the issue is probably something along the line of:<p>Every new type of thing adds a new dimension / fold / layer, and operations that transfer between layers can occur in any cycle. This leads to an exponentially complex area of valid states in a high-dimensional setting, likely with upper and lower bounds as the shape exists across dimensions. This sounds possibly intractable to define the more potential actions / actors are involved. Thus it is very difficult to reach or process an equation that defines said shape and thus validates if a co-ordinate within the system space exists on or within the surface of the valid states of the system.
This problem has a deep connection to formal methods: one of the first formal models of concurrent computing was Petri nets, which are equivalent to VASes. Petri nets are <i>very</i> limited in what they can model, and so finding reachability even those tiny, limited programs is HACK-complete!<p>What I love so much about this is that it's <i>really hard</i> to find intuitive examples of TOWER-complete or even 2-EXPTIME-complete programs, but this one is so much harder than all of them but can easily be explained to a fifth-grader.<p>Next goal is to find an intuitive HYPERACK problem...
I often wonder if the math for evolution is a similar problem.<p>There's only a limited string of code that will survive and thrive.<p>There's a set of evolutionary milestones or versions that need to happen to get where we are.<p>There's a fixed amount of time on earth or perhaps the universe.<p>Is there really enough time for all those dice roles?
> “That’s a very natural restriction for a model of reality,” said Wojciech Czerwiński, a computer scientist at the University of Warsaw. “You cannot have a negative number of apples.”<p>I realize this is probably outside the interest bounds of the problem space, but I could indeed have negative apples if I owe someone apples I don’t have.
Not exactly related, but still a fun article that covers tetration and how stupidly big simple systems can get.<p><a href="https://waitbutwhy.com/2014/11/1000000-grahams-number.html" rel="nofollow noreferrer">https://waitbutwhy.com/2014/11/1000000-grahams-number.html</a>
Interesting result. That's far faster growing than I would have anticipated since it seems intuitively like taking steps in a n-dimensional space which does grow fast, just not in a tetrative sense.
> There’s just one catch: No component of the vector describing the system’s state can ever drop below zero.<p>Maybe, this is why we need debt in an economic system, otherwise, certain transactions become intractable.