# jacobt comments on A Series of Increasingly Perverse and Destructive Games

• Game1 has been done in real life (with­out the mur­der): http://​​djm.cc/​​bignum-re­sults.txt

Also:

Write a pro­gram that gen­er­ates all pro­grams shorter than length n, and finds the one with the largest out­put.

Can’t do that, un­less you already know the pro­grams will halt. The win­ner of the ac­tual con­test used a similar strat­egy, us­ing pro­grams in the calcu­lus of con­struc­tions so they are guaran­teed to halt.

For Game2, if your op­po­nent’s pro­gram (say there are only 2 play­ers) says to re­turn your pro­gram’s out­put + 1, then you can’t win. If your pro­gram ever halts, they win. If it doesn’t halt, then you both lose.

• The win­ner of the ac­tual con­test used a similar strat­egy, us­ing pro­grams in the calcu­lus of con­struc­tions so they are guaran­teed to halt.

Whelp, that’s it, then. Ralph Loader has dis­cov­ered the largest in­te­ger.

• Can’t do that, un­less you already know the pro­grams will halt.

Wait, I get that we can’t solve the Halt­ing Prob­lem in gen­eral. But if we re­strict our­selves to pro­grams of less than a given length, are you sure there is no halt­ing al­gorithm that can analyse them all? There cer­tainly is one, for very small sizes. I don’t ex­pect it would break down for larger sizes, only for ar­bi­trary sizes.

• For ev­ery n, a pro­gram ex­ists that will solve the halt­ing prob­lem for pro­grams up to length n, but the size of this pro­gram must grow with n. I don’t re­ally see any prac­ti­cal way for a hu­man to write this pro­gram other than gen­er­at­ing an ex­tremely large num­ber and then test­ing all pro­grams up to length n for halt­ing within this bound, in which case you’ve already pretty much solved the origi­nal prob­lem. If you use some proof sys­tem to try to prove that pro­grams halt and then take the max­i­mum run­ning time of only those, then you might as well use a for­mal­ism like the calcu­lus of con­struc­tions.

• I don’t re­ally see any prac­ti­cal way for a hu­man to write this pro­gram other than gen­er­at­ing an ex­tremely large num­ber and then test­ing all pro­grams up to length n for halt­ing within this bound, in which case you’ve already pretty much solved the origi­nal prob­lem.

Wait, its even worse. A hu­man in a room is an al­gorithm, and as such can­not solve the halt­ing prob­lem. There’s got to be some pro­grams we just can’t know if they will halt or not. Which means there’s got to be an `n` be­yond which some pro­grams of length `n` or less can­not be analysed by hu­mans.

That, or we have some spe­cial magic in us.