Escaping the Infinite Blackboard

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.

Thanks to boboquack and Gareth McCaughan for completing the proof.