3
\$\begingroup\$

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 the algorithm to as few bytes as possible.

Submission Rules

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).

System Specifications

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

Answer Validation

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

  1. An English-language overview of what your algorithm computes, how it works, and why the output is mathematically interesting.
  2. 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.
  3. The golfed solution you want to submit to the aliens. This is what bytes will be scored on / cities glassed.
  4. An explanation of the modifications taken to increase the runtime of your 2. code to the runtime of your 3. code.
  5. 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.

\$\endgroup\$

closed as unclear what you're asking by xnor, Sriotchilism O'Zaic, officialaimm, pajonk, Mr. Xcoder Aug 13 '17 at 8:43

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Does a backstory involving aliens and a large cluster really make a case for adding new tags? Looks like site-clutter to me. \$\endgroup\$ – Jonathan Allan Aug 13 '17 at 2:20
  • \$\begingroup\$ @JonathanAllan Removed. \$\endgroup\$ – Techrocket9 Aug 13 '17 at 2:24
  • \$\begingroup\$ Yet the new tags still exist - probably only mods who can delete those. \$\endgroup\$ – Jonathan Allan Aug 13 '17 at 2:26
  • \$\begingroup\$ Can we theoretically extend size of integers or doubles in some languages which have constant-sized numerical variables? For example in JavaScript integer is 32-bit by spec definition no matter if you're running it on 32-bit or 64-bit machine. \$\endgroup\$ – user72349 Aug 13 '17 at 2:30
  • 1
    \$\begingroup\$ I think the conditions are much too vague and the competition will largely be in justifying being somewhat mathematically interesting and meaningfully using many threads. \$\endgroup\$ – xnor Aug 13 '17 at 4:00