loup-vaillant comments on A Series of Increasingly Perverse and Destructive Games - Less Wrong

11 Post author: nigerweiss 14 February 2013 09:22AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (33)
Tags: game theory heaven scenario hell fun torture acausal joke

Comments (33)

You are viewing a single comment's thread. Show more comments above.

Comment author: jacobt 15 February 2013 09:35:53PM *  2 points [-]

Game1 has been done in real life (without the murder): http://djm.cc/bignum-results.txt

Also:

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.

Comment author: loup-vaillant 16 February 2013 04:02:40PM *  0 points [-]

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.

Comment author: jacobt 16 February 2013 08:57:43PM *  2 points [-]

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.

Comment author: loup-vaillant 19 February 2013 09:51:27PM *  1 point [-]

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.

That, or we have some special magic in us.

Powered by Reddit Powered by Reddit