Write a program that generates all programs shorter than length n, and finds the one with the largest output.
Can’t do that, unless you already know the programs will halt. The winner of the actual contest used a similar strategy, using programs in the calculus of constructions so they are guaranteed to halt.
For Game2, if your opponent’s program (say there are only 2 players) says to return your program’s output + 1, then you can’t win. If your program ever halts, they win. If it doesn’t halt, then you both lose.
Can’t do that, unless you already know the programs will halt.
Wait, I get that we can’t solve the Halting Problem in general. But if we restrict ourselves to programs of less than a given length, are you sure there is no halting algorithm that can analyse them all? There certainly is one, for very small sizes. I don’t expect it would break down for larger sizes, only for arbitrary sizes.
For every n, a program exists that will solve the halting problem for programs up to length n, but the size of this program must grow with n. I don’t really see any practical way for a human to write this program other than generating an extremely large number and then testing all programs up to length n for halting within this bound, in which case you’ve already pretty much solved the original problem. If you use some proof system to try to prove that programs halt and then take the maximum running time of only those, then you might as well use a formalism like the calculus of constructions.
I don’t really see any practical way for a human to write this program other than generating an extremely large number and then testing all programs up to length n for halting within this bound, in which case you’ve already pretty much solved the original problem.
Wait, its even worse. A human in a room is an algorithm, and as such cannot solve the halting problem. There’s got to be some programs we just can’t know if they will halt or not. Which means there’s got to be an n beyond which some programs of length n or less cannot be analysed by humans.
Game1 has been done in real life (without the murder): http://djm.cc/bignum-results.txt
Also:
Can’t do that, unless you already know the programs will halt. The winner of the actual contest used a similar strategy, using programs in the calculus of constructions so they are guaranteed to halt.
For Game2, if your opponent’s program (say there are only 2 players) says to return your program’s output + 1, then you can’t win. If your program ever halts, they win. If it doesn’t halt, then you both lose.
Whelp, that’s it, then. Ralph Loader has discovered the largest integer.
Wait, I get that we can’t solve the Halting Problem in general. But if we restrict ourselves to programs of less than a given length, are you sure there is no halting algorithm that can analyse them all? There certainly is one, for very small sizes. I don’t expect it would break down for larger sizes, only for arbitrary sizes.
For every n, a program exists that will solve the halting problem for programs up to length n, but the size of this program must grow with n. I don’t really see any practical way for a human to write this program other than generating an extremely large number and then testing all programs up to length n for halting within this bound, in which case you’ve already pretty much solved the original problem. If you use some proof system to try to prove that programs halt and then take the maximum running time of only those, then you might as well use a formalism like the calculus of constructions.
Wait, its even worse. A human in a room is an algorithm, and as such cannot solve the halting problem. There’s got to be some programs we just can’t know if they will halt or not. Which means there’s got to be an
nbeyond which some programs of lengthnor less cannot be analysed by humans.That, or we have some special magic in us.