2
$\begingroup$

You wake up in a world with an infinite blackboard and hear a voice. "Let's play a little game. In front of you is a infinite blackboard. You may create a new number by adding a power of $2$ to an existing number, or taking two preexisting numbers $a, b$ and writing down $a \mod b.$ If you wish to escape, you will have to write down a number of my choosing subject to these rules, but I have to warn you that the number is going to be very large. How large? Let me put it this way: It's $G+T$ where $G$ is Graham's number and $T =$ TREE(3). Right now, only $0$ is written on the board. I think that should be a good place to start."

"I almost forgot to mention! Just as a little bonus, I've given you a magic machine. If you select $x$ and describe an algorithm for computing a non-negative integer $k,$ it will run the algorithm for you and write $x+2^k$ on the board in a blink of an eye - $100$ milliseconds. If you select numbers $a, b,$ it will instantly compute and write down $a \mod b$ for you, again taking $100$ ms. You can sit back and tell it to repeatedly increment by $1,$ but I'm sure you'll be driven insane long before you can get out of here. Good luck!"

Clarifications:

  1. $a \mod b$ is a value in $[0, b).$ More precisely, if $a = pb+q$ where $0 \le q < b,$ then $a \mod b = q.$
  2. The machine does not have any powers beyond those described. You cannot have it start incrementing by $1,$ and then tell it to put you to sleep and wake you when it's finished.
  3. You must write down the exact number, not a larger number that contains $G+T$ among its digits.
$\endgroup$
  • $\begingroup$ What numbers are available at the very beginning? All the operations need at least one pre-existing number. $\endgroup$ – Toby Mak Aug 2 at 9:28
  • 1
    $\begingroup$ @TobyMak Only $0.$ Fixed now. $\endgroup$ – Display name Aug 2 at 9:36
  • $\begingroup$ "If you wish to escape, you will have to write down a number of my choosing" - Surely you just write down, "G+T". Please say precisely what you mean by "write down". Do you want all the digits? $\endgroup$ – chasly - reinstate Monica Aug 2 at 9:55
  • $\begingroup$ @reinstate Monica You have to write down the number subject to the rules for writing down a new number described earlier. Fixed. $\endgroup$ – Display name Aug 2 at 10:11
  • $\begingroup$ Must k be an integer? Must k be non-negative? $\endgroup$ – boboquack Aug 2 at 10:42
1
$\begingroup$

Since there seems to be no limit on the algorithm provided to compute the exponent - it will run any algorithm in 100ms - this can be done in just a few steps.

$G$ and $T$ are already defined by algorithms, even though the algorithm for $T$ would be a brute-force search. So the machine can internally compute $G+T$ in 100ms, even though it can't write it down directly.

Rather than focus on $G+T$, you can get the machine to write down any number as $2^m \bmod 5^n$ as long as $5^n$ is greater than your number, since 2 is a primitive root of any power of 5. The machine can easily compute $m$ and $n$ here, but can't easily write $5^n$ directly. There's one catch here though. If our target number is a multiple of 5, then it's not covered. However, in that case, you can use this algorithm to get one less than the target and add one to it, and you can ask the machine to test whether you need this step or not.

$2^x \bmod 2^x-5 = 5$, and this can be raised to an arbitrary power so that $2^{nx} \bmod 2^x-5 = 5^n$ as long as $5^n < 2^x-5$, so pick a large enough $x$. Now, the machine can't easily write down $2^x-5$ either.

$2^x-5 = 2^{x+1} \bmod 2^x+5$ and this the machine can write down in 5 steps. Then another 2 steps for $2^{nx}$ and the next mod operation. Then two more for $2^m$ and the last mod operation. Plus one step to determine if the target is a multiple of 5, and if so one more step to add 1. As an example take a target of 15. This is a multiple of 5, so our target is 14. $5^2=25>14$ so $n=2$ and $2^6 \bmod 5^2 = 14$. To get the $5^2$, $2^5-5=27>5^2$, so $x=5$ (coincidentally), and $2^{10} \bmod 27 = 25$. Finally, $2^6 \bmod 2^5+5 = 27$.

Thanks to boboquack and Gareth McCaughan for completing the proof.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It's not even known that there are infinitely many primes (with no further conditions on their form) with 2 as a primitive root. $\endgroup$ – Gareth McCaughan Aug 2 at 23:22
  • $\begingroup$ Is it known that there are infinitely many numbers with a primitive root of 2? There's nothing in this that needs it to be a prime. (I can't find many good resources on what's currently known about primitive roots beyond the basics covered by Wikipedia and Mathworld, if you have any good references.) $\endgroup$ – Joshua Taylor Aug 3 at 1:49
  • 1
    $\begingroup$ I note that if you can find a way to construction 2^k-5 efficiently for large k, then for any n choose a k>log_2(5)n and then 2^(nk) mod 2^k-5 would be 5^n. $\endgroup$ – boboquack Aug 3 at 14:20
  • 1
    $\begingroup$ Oh and right 2^(k+1) mod 2^k+5 = 2^k-5 completing the solution $\endgroup$ – boboquack Aug 3 at 14:23
  • 1
    $\begingroup$ You can hack the 5|G+T case pretty easily. First ask the machine to write down 2^0 if 5|G+T and 2^1 if not. If 5|G+T then derive G+T-1 instead and then ask the machine to add 1 to it. $\endgroup$ – Gareth McCaughan Aug 4 at 13:02
3
$\begingroup$

You're not going to like this, but:

"OK, machine, listen up. I'm going to describe an algorithm for you, and it's a little bit complicated. First of all, let me define a Turing machine for you, along with a simple numerical representation for what's called a Turing machine's state table. [Do this. I promise I can.] And now let me define for you the notions of formal system, proof, and Zermelo-Fraenkel set theory. [Do this. Again, I promise I can.] Note that in the language of ZF set theory we can formalize the notion of Turing machine, and the proposition that a given machine halts. Now consider all possible finite strings in the language of ZF set theory. Some of them are mathematical proofs whose conclusion is of the form "The Turing machine with such-and-such state table, when run with an initially blank tape, eventually halts with the tape containing some number N." and obviously you can recognize those purely syntactically. So, say that a number $n$ is good if it's the representation of the state table of a Turing machine for which there is such a proof of length at most G+T steps. In this case, write $N(n)$ for the number $N$ it computes. OK so far? Now, I want you to enumerate all finite sequences of positive integers, and for each one I want you to simulate what you would do with a certain sequence of instructions derived from that sequence of integers. The integer $2^a3^b$, where $b$ is good, means "write down the $a$th number on the board plus $2^{N(n)}$. The integer $2^a5^b$ means "write down the $a$th number on the board modulo the $b$th number on the board". Other integers mean "do nothing". Still following? Splendid. So you need to do this for all finite sequences of positive integers, ordered by total length of all the integers and however you like subject to that. And the first time you find one of these sequences for which the simulated board ends up with G+T written on it, you then need to find the smallest power of 2 whose base-10 digits begin with an encoding of that sequence of numbers, defined as follows: encode $2^a3^b$ as 10A0B0 and $2^a5^b$ as 20A0B0 where A,B are derived from a,b by writing those numbers in base 7 and adding 3 to all their digits, and then concatenate everything to gether. Finally, when you've got that power of 2, please add that power of 2 to the 0 that's actually on the board and write down the result for me."

100ms later, I have on the board what may be a fairly monstrous number, but its digits begin with instructions telling me a nice efficient way (if there is one) to get the machine to put G+T on the board.

Obviously this isn't really in the spirit of the thing, but it definitely works :-).

(I do have some hazy ideas for how to do it better, but I have other things I need to do today so probably someone else will solve this properly before I do. That's OK.)

Discussion in comments has made it clear that what I wrote above isn't as clear as one might like, so let me explain in more detail what's going on; hopefully that will clarify both why it works and why it obviously isn't remotely what the question is looking for.

Our machine is terrifyingly powerful; it can perform any calculation we demand. But it has this annoying restriction that, in effecy, it can only output powers of 2 when it does it. Clearly the intended approach is to have it use that terrifying power to calculate something (or some things) from which G+T can be derived in a fairly simple way using the "adding powers of 2" and "modulus" operations we have. My approach will end up doing that, but it begins with a surely-unintended exploitation of the machine's power.

I want to get the machine to solve the puzzle for me. That is, to work out a short sequence of operations I can instruct it to perform, which has the result that we end up with G+T on the board. And I want to do it in a way that works even though the terrifying algorithmic power can only be used to generate powers of 2.

Well, solving the puzzle is itself an algorithmic matter! That is, we can set the machine to searching through all possible sets of instructions I could give it, in something like order of complexity, until it finds a set of instructions such that after performing them G+T is on the board.

There are three difficulties. First, is that really an algorithmic matter? Second, how can I express it in terms the machine can make any sense of? Third, how can I make use of the answer when the machine can only perform arbitrary calculations whose answer is a power of 2?

The answer to the first question is: yes, provided what I ask the machine to search through is provably terminating algorithms rather than just algorithms that do in fact terminate, because one can enumerate proofs mechanically.

The answer to the second question is: by casting my question in purely algorithmic form, which requires me to explain explicitly what an algorithm is and what a proof is, so that I can get the machine to enumerate proofs that algorithms terminate.

The answer to the third question is: by exploiting the fact that the puzzle involves an actual physical blackboard on which numbers are actually written -- I assume in base 10, but one could adapt this to any other reasonable system. So when the machine has found a procedure that will generate G+T, I get it to write down a number whose base-10 representation begins with a description of the procedure it found.

With all this understood, a fourth question arises: How do I make sure the procedure the machine finds is short enough that I can actually perform it? The algorithm described above was intended (it had a bug; see below) to have it enumerate sequences of algorithms in (more or less) order of the length of the shortest proofs that the algorithms terminate, which will produce procedures with short termination proofs, which isn't quite the same thing. I bet that this would actually produce something manageable, but what I really want is enumeration in order of the length of the algorithms' descriptions rather than of their termination proofs. This is more difficult because one can't enumerate terminating algorithms as such. But if we're prepared to accept, say, only algorithms that can be proved to terminate with proofs using no more than G+T steps -- I'm prepared to bet that we don't need more than that, because otherwise the puzzle would be unfair -- then we can do that just as easily.

And in fact I notice, on rereading my description of the algorithm, that I slipped up and wrote something intermediate between those two things, which is actually uncomputable. So I'm fixing it up the second way, so that now it looks for simplest algorithms (meaning smallest Turing machine) with termination proofs no longer than G+T, instead of looking for shortest termination proofs.

So, to be clear about what I actually do: I give the machine the instructions above, with the gaps filled in. I wait 100ms. The blackboard now contains a (presumably quite large, but not too monstrous) power of 2. The digits of this power of 2, reading from the left, contain explicit instructions specifying a sequence of things to ask the machine to do, each step being one of the two kinds permitted. So I read this number and issue the machine with those instructions.

A few details: (1) Although I said $2^a3^b$ and $2^a5^b$ when describing how to encode the procedure, actually that would be painful to decode. Better to make it a digit-concatenation thing like I did for the overall sequence. (2) When following the procedure the machine has found for me, I need to remember that there's now one more number on the blackboard than before I started. (3) Of course you could invalidate this whole approach by replacing the blackboard with, say, a computer memory accessible to the machine but not to me.

| improve this answer | |
$\endgroup$
  • $\begingroup$ How do you plan to reach $G+T$ from the power of $2$ you just asked for? Your "nice efficient way" seems to involve performing an insanely large number of steps after you obtain the power of $2.$ In fact, I suspect whatever operations you haven't described yet will take longer than asking the machine to repeatedly increment by $1.$ $\endgroup$ – Display name Aug 2 at 10:09
  • 1
    $\begingroup$ I don't need to plan! The machine is doing all the planning for me :-). I will reach G+T from the power of 2 it gave me by following the instructions encoded into the power of 2 it hands me. $\endgroup$ – Gareth McCaughan Aug 2 at 15:51
  • $\begingroup$ (I should maybe say that it's known, and fairly easy to prove, that every string of base-10 digits occurs at the beginning of some power of 2, so that "the smallest power of 2 ..." at the end is guaranteed to exist.) $\endgroup$ – Gareth McCaughan Aug 2 at 15:51
  • 1
    $\begingroup$ And no, none of what I have described will take anywhere remotely like as long as just asking the machine to keep incrementing by 1. The bits I put in square brackets are omitted only because they're standard and not very interesting as far as solving this puzzle goes. It would take less than, let's say, an hour to fill in all the details, assuming -- as I think we have to -- that the machine is capable of understanding anything expressed explicitly and algorithmically. $\endgroup$ – Gareth McCaughan Aug 2 at 15:54
  • $\begingroup$ I'm talking about all the steps that you need to take after you have this massive power of $2.$ What modulus are you going to use, and what new numbers are you going to introduce? You want to write down $G+T$ exactly, not write down a larger number that has $G+T$ in its digits. Else, there is an easier solution using Dirichlet's irrational approximation theorem and the irrationality of $\log_{10} 2.$ $\endgroup$ – Display name Aug 3 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.