raganwald
(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?



  1. 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:
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...
 
Paul:

I play the 3M version, and like it immensely. If your travels bring you to Toronto...
 




<< Home
Reg Braithwaite


Recent Writing
Homoiconic Technical Writing / raganwald.posterous.com

Books
What I‘ve Learned From Failure / Kestrels, Quirky Birds, and Hopeless Egocentricity

Share
rewrite_rails / andand / unfold.rb / string_to_proc.rb / dsl_and_let.rb / comprehension.rb / lazy_lists.rb

Beauty
IS-STRICTLY-EQUIVALENT-TO-A / Spaghetti-Western Coding / Golf is a good program spoiled / Programming conventions as signals / Not all functions should be object methods

The Not So Big Software Design / Writing programs for people to read / Why Why Functional Programming Matters Matters / But Y would I want to do a thing like this?

Work
The single most important thing you must do to improve your programming career / The Naïve Approach to Hiring People / No Disrespect / Take control of your interview / Three tips for getting a job through a recruiter / My favourite interview question

Management
Exception Handling in Software Development / What if powerful languages and idioms only work for small teams? / Bricks / Which theory fits the evidence? / Still failing, still learning / What I’ve learned from failure

Notation
The unary ampersand in Ruby / (1..100).inject(&:+) / The challenge of teaching yourself a programming language / The significance of the meta-circular interpreter / Block-Structured Javascript / Haskell, Ruby and Infinity / Closures and Higher-Order Functions

Opinion
Why Apple is more expensive than Amazon / Why we are the biggest obstacles to our own growth / Is software the documentation of business process mistakes? / We have lost control of the apparatus / What I’ve Learned From Sales I, II, III

Whimsey
The Narcissism of Small Code Differences / Billy Martin’s Technique for Managing his Manager / Three stories about The Tao / Programming Language Stories / Why You Need a Degree to Work For BigCo

History
06/04 / 07/04 / 08/04 / 09/04 / 10/04 / 11/04 / 12/04 / 01/05 / 02/05 / 03/05 / 04/05 / 06/05 / 07/05 / 08/05 / 09/05 / 10/05 / 11/05 / 01/06 / 02/06 / 03/06 / 04/06 / 05/06 / 06/06 / 07/06 / 08/06 / 09/06 / 10/06 / 11/06 / 12/06 / 01/07 / 02/07 / 03/07 / 04/07 / 05/07 / 06/07 / 07/07 / 08/07 / 09/07 / 10/07 / 11/07 / 12/07 / 01/08 / 02/08 / 03/08 / 04/08 / 05/08 / 06/08 / 07/08 /