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.

That, or we have some special magic in us.

A Series of Increasingly Perverse and Destructive Games

by nigerweiss 3 min read14th Feb 201333 comments

11


Related to: Higher Than the Most High

 

The linked post describes a game in which (I fudge a little), Omega comes to you and two other people, and ask you to tell him an integer.  The person who names the largest integer is allowed to leave.  The other two are killed.

This got me thinking about variations on the same concept, and here's what I've come up, taking that game to be GAME0.  The results are sort of a fun time-waster, and bring up some interesting issues.  For your enjoyment...

 

THE GAMES:

GAME1: Omega takes you and two strangers (all competent programmers), and kidnaps and sedates you.  You awake in three rooms with instructions printed on the wall explaining the game, and a computer with an operating system and programming language compiler, but no internet.  Food, water, and toiletries are provided, but no external communication.  The participants are allowed to write programs on the computer in a language that supports arbitrarily large numerical values.  The programs are taken by Omega and run on a hypercomputer in finite time (this hypercomputer can resolve the halting problem and infinite loops, but programs that do not eventually halt return no output).  The person who wrote the program with the largest output is allowed to leave.  The others are instantly and painlessly killed.  In the event of a tie, everyone dies.  If your program returns no output, that is taken to be zero.    

GAME2: Identical to GAME1, except that each program you write has to take two inputs, which will be the text of the other players' programs (assume they're all written in the same language).  The reward for outputting the largest number apply normally.  

GAME3: Identical to Game2, except that while you are sedated, Omega painlessly and imperceptibly uploads you.  Additionally, the instructions on the wall now specify that your program must take four inputs - blackbox functions which represent the uploaded minds of all three players, plus a simulation of the room you're in, indistinguishable from the real thing.  We'll assume that players can't modify or interpret the contents of their opponents' brains.  The room function take an argument of a string (which controls the text printed on the wall, and outputs whatever number the person in the simulation's program returns).

 

In each of these games, which program should you write if you wish to survive?  

 

SOME DISCUSSION OF STRATEGY: 

GAME1: Clearly, the trivial strategy (implement the Ackerman or similar fast-growing functions and generate some large integer), gives no better than random results, because it's the bare minimal strategy anyone will employ, and your ranking in the results, without knowledge of your opponents is entirely up to chance / how long you're willing to sit there typing nines for your Ackermann argument.

A few alternatives for your consideration:

1: if you are aware of an existence hypothesis (say, a number with some property which is not conclusively known to exist and could be any integer), write a program that brute-force tests all integers until it arrives at an integer which matches the requirements, and use this as the argument for your rapidly-growing function.  While it may never return any output, if it does, the output will be an integer, and the expected value goes towards infinity.  

2: Write a program that generates all programs shorter than length n, and finds the one with the largest output.  Then make a separate stab at your own non-meta winning strategy.  Take the length of the program you produce, tetrate it for safety, and use that as your length n.  Return the return value of the winning program.

On the whole, though, this game is simply not all that interesting in a broader sense.  

GAME2: This game has its own amusing quirks (primarily that it could probably actually be played in real life on a non-hypercomputer), however, most of its salient features are also present in GAME3, so I'm going to defer discussion to that.  I'll only say that the obvious strategy (sum the outputs of the other two players' programs and return that) leads to an infinite recursive trawl and never halts if everyone takes it.  This holds true for any simple strategy for adding or multiplying some constant with the outputs of your opponents' programs.    

 

GAME3: This game is by far the most interesting.  For starters, this game permits acausal negotiation between players (by parties simulating and conversing with one another).  Furthermore, anthropic reasoning plays a huge role, since the player is never sure if they're in the real world, one of their own simulations, or one of the simulations of the other players.  

Players can negotiate, barter, or threaten one another, they can attempt to send signals to their simulated selves (to indicate that they are in their own simulation and not somebody else's).  They can make their choices based on coin flips, to render themselves difficult to simulate.  They can attempt to brute-force the signals their simulated opponents are expecting.  They can simulate copies of their opponents who think they're playing any previous version of the game, and are unaware they've been uploaded.  They can simulate copies of their opponents, observe their meta-strategies, and plan around them.  They can totally ignore the inputs from the other players and play just the level one game.  It gets very exciting very quickly.  I'd like to see what strategy you folks would employ.  

 

And, as a final bonus, I present GAME4 :  In game 4, there is no Omega, and no hypercomputer.  You simply take a friend, chloroform them, and put them in a concrete room with the instructions for GAME3 on the wall, and a linux computer not plugged into anything.  You leave them there for a few months working on their program, and watch what happens to their psychology.  You win when they shrink down into a dead-eyed, terminally-paranoid and entirely insane shell of their former selves.  This is the easiest game.  

 

Happy playing!   

 

 

11