(This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)
Tuesday, April 03, 2007
Hypergame II
Reg! An occasional rant on etiquette is interesting, but I read your blog to reconnect with my love of software. Do you still love what you do, or have you turned into one of those incoherent rage artists that has nothing better to do than stir up wasp nests and trade flames on programming.reddit.com?
Err, thanks. I’ve been chewing Kibble for a few days, and I needed to get back to what I love.1 So here’s a meandering dump of something on my mind. There is no particular point to this post, it’s just a way I have of reminding myself how much fun being well enough to wonder “why?” really is.
My brother-in-law was in town this past weekend, and we enjoyed a Sunday afternoon game of Acquire
. Formal games are much on my mind lately, thanks to the last Amazon delivery dropping On Numbers and Games
on my doorstep.
Thinking about games reminded me William Zwicker’s Hypergame pseudo-paradox, and that made me wonder how to describe it using programs instead of games. I came up with the following:
“You have a computer. By which I mean any computer, real, imaginary, even an idealized Turing machine. It runs programs, obviously. Now programs on this computer are finite or infinite. By which I mean, a finite program always halts eventually, and an infinite program does not always halt eventually. Note that an infinite program might halt or it might not. perhaps it contains some randomization element. Perhaps it has different inputs that cause it to do different things.
“Now let’s posit the idea of an algorithm that can examine a program for this machine and determine whether it is finite or infinite. Note that this algorithm need not be a program that runs on the machine, we allow that it can live “outside” the machine.
“I ask you this question: the computer you are thinking of, can we write a bootstrap program (or “bootstrapper”) for this computer? In other words, can we write a program that loads and executes other programs? Or more generally, does this computer support self-reference in programs?
“Consider a general bootstrapper for the computer. Is it a finite program or an infinite program? Obviously, it is an infinite program, because it can load and execute any other program, and if it loads an infinite program, then its own execution will be infinite.
“But what if we write a restricted version of the bootstrapper: it will only load finite programs. Maybe we mark those programs with a special bit, maybe it just trusts us not to cheat and give it an infinite program.
Is the restricted bootstrapper a finite program?
“If it only loads finite programs, you would think it is finite. After all, it loads and executes a program that runs in finite time, so it must execute in finite time. But if that’s the case, why can’t the restricted boostrapper load itself? It loads and runs finite programs, and if it’s a finite program then it can load and execute itself!
“In that case, it isn’t a finite program. Whew! Wait a second, if it isn’t a finite program, then the pseudo-paradox disappears, and we’re back to the fact that it must run in finite time. So it is a finite program!”
Well, there are lots of ways to explain this, and they’re all interesting. You can posit that the halting problem is undecidable, as Alan Turing
did. If so, we have just proven it for an interesting case, where we allow the computation of whether a program halts outside of the computation space of our machine.
You can also note that the problem goes away if our computer is too simple to allow self-reference. That’s an important result in its own right.
You can wonder whether “finite” is one of those things that has at least three states: true, false, and “strange.” Does allowing “strange” as the result of your “finite test algorithm” remove the paradox?
Reg! An occasional rant on etiquette is interesting, but I read your blog to reconnect with my love of software. Do you still love what you do, or have you turned into one of those incoherent rage artists that has nothing better to do than stir up wasp nests and trade flames on programming.reddit.com?
Err, thanks. I’ve been chewing Kibble for a few days, and I needed to get back to what I love.1 So here’s a meandering dump of something on my mind. There is no particular point to this post, it’s just a way I have of reminding myself how much fun being well enough to wonder “why?” really is.
My brother-in-law was in town this past weekend, and we enjoyed a Sunday afternoon game of Acquire
. Formal games are much on my mind lately, thanks to the last Amazon delivery dropping On Numbers and Games on my doorstep.Thinking about games reminded me William Zwicker’s Hypergame pseudo-paradox, and that made me wonder how to describe it using programs instead of games. I came up with the following:
“You have a computer. By which I mean any computer, real, imaginary, even an idealized Turing machine. It runs programs, obviously. Now programs on this computer are finite or infinite. By which I mean, a finite program always halts eventually, and an infinite program does not always halt eventually. Note that an infinite program might halt or it might not. perhaps it contains some randomization element. Perhaps it has different inputs that cause it to do different things.
“Now let’s posit the idea of an algorithm that can examine a program for this machine and determine whether it is finite or infinite. Note that this algorithm need not be a program that runs on the machine, we allow that it can live “outside” the machine.
“I ask you this question: the computer you are thinking of, can we write a bootstrap program (or “bootstrapper”) for this computer? In other words, can we write a program that loads and executes other programs? Or more generally, does this computer support self-reference in programs?
“Consider a general bootstrapper for the computer. Is it a finite program or an infinite program? Obviously, it is an infinite program, because it can load and execute any other program, and if it loads an infinite program, then its own execution will be infinite.
“But what if we write a restricted version of the bootstrapper: it will only load finite programs. Maybe we mark those programs with a special bit, maybe it just trusts us not to cheat and give it an infinite program.
Is the restricted bootstrapper a finite program?
“If it only loads finite programs, you would think it is finite. After all, it loads and executes a program that runs in finite time, so it must execute in finite time. But if that’s the case, why can’t the restricted boostrapper load itself? It loads and runs finite programs, and if it’s a finite program then it can load and execute itself!
“In that case, it isn’t a finite program. Whew! Wait a second, if it isn’t a finite program, then the pseudo-paradox disappears, and we’re back to the fact that it must run in finite time. So it is a finite program!”
Well, there are lots of ways to explain this, and they’re all interesting. You can posit that the halting problem is undecidable, as Alan Turing
did. If so, we have just proven it for an interesting case, where we allow the computation of whether a program halts outside of the computation space of our machine.You can also note that the problem goes away if our computer is too simple to allow self-reference. That’s an important result in its own right.
You can wonder whether “finite” is one of those things that has at least three states: true, false, and “strange.” Does allowing “strange” as the result of your “finite test algorithm” remove the paradox?
- Speaking of which, Purely Functional Data Structures
arrived in the mail and I’m looking forward to writing about the relationship between Copy on Write semantics and Multi-Version Concurrency-Control protocols for arbitrating shared-memory threaded applications.
Comments on “Hypergame II”:
<< Home
Excellent. Acquire was one of the games my family played when I was a kid, although it was the venerable 3M Bookshelf Games version as opposed to the more modern Avalon Hill version. Don't tell me you also have Twixt, too...
<< Home
