[D_Alex]

Yes - I was just thinking the same thing. I have not come to a conclusion one way or another on whether it is possible to de-couple the generating program from the generated programs for the purpose of analysing the proof. It seems that there should be a way to do it... unfortunately I cannot spend more time on this now.

[jawarner]

Does there have to be a generating program? The set of all finite programs is countable, so it could not possibly describe the uncountable set of real numbers - this would be a surjection from a countable set to an uncountable set. In particular only the subset of computable numbers [1] can be described by the countable set of finite computer programs.

Also, any infinite program either passes through a finite number of instructions or never terminates. So any program which does not have a finite representation will never terminate.

[1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[drdeca]

What if the function takes input, and for each input, the program halts, but for every instruction, there is an input such that the program when run on that input will execute that instruction? Would that imply a contradiction? It doesn't seem like it to me. Yeah, no, that should be fine.

Example: consider a language where 0 means "if the input register is at most 0, halt with the answer "no", otherwise, decrement the input register and continue to the next instruction" and 1 means the same thing except that it gives the answer "yes" instead.

Then the fractional part of any real, expressed in binary, would be a program that takes an integer as input, and answers whether that digit of the number is 1. This seems like it would count as a program to me.

So, this would allow there to be uncountably many "programs", only, almost all of them would be impossible for us to refer to specifically.

Hey, this way you could define a uniform measure over programs. Hah.

Wait, is that how Solomonoff induction stuff works? (Of course, with a richer language than what I described)