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