Aliens have arrived, and they aren't friendly.
Turns out, they've been in the process of converting all matter in the universe into compute capability so they can have more fun in their VR simulations.
Our solar system is the last bit of space they haven't converted yet, and they're about to remedy this oversight.
However! As "payment" for the use of our matter, the aliens are generously allowing us to run one computation on their universe-sized compute cluster before they convert us to compute units.
After world leaders conferred on how to handle this crisis, you were tasked with creating an algorithm to run on the alien cluster which will not complete before the heat death of the universe, thus forestalling our demise.
However, internally the aliens charge back the cost of using the cluster by the number of bytes of code submitted, so the alien philanthropy division which is making us this generous offer and footing the bill is incentivizing us to keep our code short by glassing one of our cities (in descending population order) for every byte of code we submit. Thus, your orders are to code-golf the algorithm to as few bytes as possible.
The aliens are smart. They will not allow you to submit code which you cannot prove complies with the following properties:
- Must halt, eventually™. The burden of proving this is on you. (Yes, the halting problem is impossible in the general case. Pick one where it isn't.)
- Must meaningfully utilize the entire cluster. If any cores would be idle or doing unnecessary computation for over half of the total runtime of the algorithm, the aliens will reject the algorithm (unnecessary means that the result would not change if that computation were skipped. Feel free to compute things in all manner of inefficient fashion).
- Must produce a result which will fit in the combined storage capacity of all human computers (assume one zettabyte is available) so we can appreciate the resulting data before we are annihilated. Write the result to stdout.
- Must produce a result that is deterministic (so take no input) and at least a little bit mathematically interesting (determining if the googolplexth digit of pi is odd is interesting; producing 42 is not).
To satisfy your bosses (the world leaders) your program must not halt until after the heat death of the universe (10¹⁰⁰ years from now).
The alien cluster is abstracted behind an API which makes it seem like a single enormous SMT x86_512 CPU.
- Every atom in the universe besides ours (10⁸⁰) functions as a 512 bit CPU core running at 900 petahertz
- Due to black holes, there is infinite zero-latency non-volatile RAM available for use during the computation, but you are still limited to the 512 bit address space (that's just under 8×10¹⁶³ yottabytes of space) and the end product has to fit within one ZB.
- Wormholes are used to address cache coherency and atomicity issues with zero latency, as long as the appropriate language-level features are used to indicate their necessity
Regrettably, I have neither access to a comparable system for testing submissions, nor the patience to see if they do in fact take until the heat death of the universe to halt. Thus, the following will be expected of a submission (please number them in your answers):
- An English-language overview of what your algorithm computes, how it works, and why the output is mathematically interesting.
- An ungolfed and scaled-down version of your problem/algorithm which can run to completion in seconds or less on normal human hardware (such as ideone). This is not scored, but used to demonstrate that you have a working algorithm.
- The golfed solution you want to submit to the aliens. This is what bytes will be scored on / cities glassed.
- An explanation of the modifications taken to increase the runtime of your
2.code to the runtime of your
- An argument for why neither the aliens nor your bosses will reject your submission. Some hand-waving is allowed here, though formal proofs earn major kudos. At a minimum, show some math relating to your loops or recursion depth against the clock speed and core count of the alien system, along with commentary on your work-breakdown strategy to saturate all the cores.
There are no programming language restrictions, as long as the resulting program can meet the constraints of the challenge. Minor kudos for use of language-level features (such as
size_t) which can run through the aliens' 512 bit compiler without requiring any work on their end.