[D_Alex]

Infinity is a weird thing, isn't it?

Now: one of the proofs in the paper relied on an assumption that all possible computer programs are countable, which I think implies that they are finite in length. But it is fairly trivial to generate computer programs that are infinitely long, say by assigning characters or expressions in some language to the digits of transcendental numbers such as pi. It is also possible to generate infinitely many such programs, simply by using pi/2, pi/3... etc.

Now, the proof as presented fails, since these programs cannot be ordered by size.

Can the proof be modified to take account of this? I don't know... comments invited.

[bo1024]

I'm not sure it's so easy to define or generate an infinitely-long program. Such a thing doesn't sound to me like it would be either possible in practice or equivalent to a Turing Machine in theory.

For example, you suggest an assignment of expressions to digits of pi. Now how would you run such a program? Presumably by generating the digits of pi, interpreting them as expressions, and evaluating the expressions, etc.

But the program you used to do that was finite. So are you running the infinite program? I think it's more fair to say you are running the finite one.

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