(

Wednesday, December 12, 2007

Have nothing in your house that you do not know to be useful, or believe to be beautiful

The title is a quote by William Morris, a man with a deep interest in design and its relationship to our place in society. I think it applies to ideas as well as artefacts, and I must warn you that the following ideas fall under “beautiful” :-)

**The Halting Problem**

(There seems to be some confusion about what this says. It says that we cannot construct*one* machine or function or program that can examine any combination of machine or program and input and then correctly decide whether the program halts or does not halt.)

**1 + 1 = Cool**

Lady or the Tiger? And Other Logic Puzzles Including a Mathematical Novel That Features Gödel’s Great Discovery: “Another scintillating collection of brilliant problems and paradoxes by the most entertaining logician and set theorist who ever lived. As in all of Professor Smullyan’s fantastic puzzle books, you end up exploring that strange subterranean region below mathematics, where Gödelian corridors lead in all directions to beautiful theorems about truth and provability.”— Martin Gardner

We absolutely *know* that the Halting Problem is true (meaning there is no function that correctly answers whether every program halts or does not halt). However, the math seems a bit gnarly if you were sleeping through your computability courses. And furthermore, just because we know that there must exist programs for which we do not know whether they will halt for at least one input, it’s always a lot more convincing to actually look at such a program.

The Wikipedia article provides a couple of examples based on unsolved problems in mathematics, the search of an odd perfect number and the search for the largest pair of twin primes. The idea is this: if you can write a program that uses brute force to search for a counter-example to an unsolved problem in mathematics, you have one of three things:

Of course, alternative four is to accept the idea that there are very simple programs that might run forever but we have no way of knowing if they ever stop.

If you go through any of the proofs of the Halting Problem, you already know this. But sometimes, an example is worth a thousand words.

**Goldbach’s Conjecture**

To review, by*unsolved problem*, we mean that we haven’t proved it is true and we also haven’t proved it is false. So here’s what we do: Let’s write a program that checks every even integer from 4 up. If it is the sum of two primes, we try the next higher even number. If it is **not** the sum of two primes, we stop and output the number.

Does this program halt? If you can answer this question, you solve a huge problem in Number Theory. Now again, this does*not* prove the Halting Problem. For one thing, we might solve the Goldbach Conjecture by proving or disproving it, and then we could tell you whether this program halts.

Another possibility is that we will prove that the Goldbach Conjecture is undecidable. In that case, we will have a proof that we cannot prove whether this program halts. This has been done with other conjectures. For example, we have proven that we can neither prove nor disprove Cantor’s Continuum Hypothesis: it appears that within Number Theory, there is no way to know whether there exist infinities that are both larger than א-null and smaller than א-one.

This program*does* demonstrate that at a deep level, programs are math. You can draw an equivalence between certain programs and certain statements in mathematics. We can say that certain properties of Program P (like whether it halts) are equivalent to certain properties of Mathematical Statement S (like whether every even number is the sum of two primes).

That connection leads us to Incompleteness. If we know that there must be mathematical statements that are undecidable (like statements that are true but cannot be proved), we know that there are undecidable properties of computer programs. And if we know that there are undecidable properties of computer programs (like whether they halt), we know that there are undecidable statements in mathematics.

I find that deeply, deeply interesting.

This was provoked by an example from the Qi language manual. It came at a good time: after writing about various aspects of our industry and its limitations, I needed to be reminded how how much I enjoy thinking about programs.

Which brings me back around to the title. Computer Science is a big field. Programming is a big field. Working for a living developing software is a big field. I believe you have to pick and choose, you can’t learn everything, you can’t try to pick up every new thing that comes along.

But I believe that if you follow Morris’ dictum, you will be effective and also deeply engaged. Do not settle for mediocre ideas. Accept only those things that are useful, beautiful, or both. Do not settle for just beautiful or just useful. It is surprising how often useful things help you build beauty, and likewise how often beautiful things turn out to be useful in a different context.

The title is a quote by William Morris, a man with a deep interest in design and its relationship to our place in society. I think it applies to ideas as well as artefacts, and I must warn you that the following ideas fall under “beautiful” :-)

The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation. The question is, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations of memory or time on the program’s execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting.The question is simply whether the given program will ever halt on a particular input.

The reason the halting problem is famous is because it is undecidable, which means there is no computable function that correctly determines which programs halt and which ones do not.

(There seems to be some confusion about what this says. It says that we cannot construct

Lady or the Tiger? And Other Logic Puzzles Including a Mathematical Novel That Features Gödel’s Great Discovery: “Another scintillating collection of brilliant problems and paradoxes by the most entertaining logician and set theorist who ever lived. As in all of Professor Smullyan’s fantastic puzzle books, you end up exploring that strange subterranean region below mathematics, where Gödelian corridors lead in all directions to beautiful theorems about truth and provability.”— Martin Gardner

The Wikipedia article provides a couple of examples based on unsolved problems in mathematics, the search of an odd perfect number and the search for the largest pair of twin primes. The idea is this: if you can write a program that uses brute force to search for a counter-example to an unsolved problem in mathematics, you have one of three things:

- You run your program, it finds a counter-example, and you win a Nobel Prize in Mathematics (not really!) for disproving the unsolved problem, or:
- You run your program, it goes on running forever, and you can’t prove that it will ever stop. But it might. If you could prove it would stop than you can also disprove the unsolved problem, so again you win a Nobel Prize in Mathematics.
- You don’t need to run your program, you know darn well it will never stop, and you can prove it will never stop. Now you have proved the unsolved problem, so again you win a Nobel Prize in Mathematics.

Of course, alternative four is to accept the idea that there are very simple programs that might run forever but we have no way of knowing if they ever stop.

If you go through any of the proofs of the Halting Problem, you already know this. But sometimes, an example is worth a thousand words.

Goldbach’s conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:Every even integer greater than 2 can be written as the sum of two primes. In other words, the Goldbach conjecture states that every even number greater than or equal to four is a Goldbach number, a number that can be expressed as the sum of two primes.

To review, by

require 'mathn'

@prime_generator = Prime.new

@primes = [@prime_generator.succ] # start with [2]

# given a number, answer a list with at least all

# of the primes <= that number. may include

# larger primes.

#

# primes_at_least_up_to(12) -> [2,3,5,7,11,13]

# and possibly more primes

#

def primes_at_least_up_to(n)

while @primes[-1] < n do

@primes << @prime_generator.succ

end

@primes

end

def sum_of_two_primes?(n)

!!(primes_at_least_up_to(n).detect { |p1|

primes_at_least_up_to(n).include?(n-p1)

})

end

n = 4

while sum_of_two_primes?(n)

n +=2

end

puts n

Does this program halt? If you can answer this question, you solve a huge problem in Number Theory. Now again, this does

Another possibility is that we will prove that the Goldbach Conjecture is undecidable. In that case, we will have a proof that we cannot prove whether this program halts. This has been done with other conjectures. For example, we have proven that we can neither prove nor disprove Cantor’s Continuum Hypothesis: it appears that within Number Theory, there is no way to know whether there exist infinities that are both larger than א-null and smaller than א-one.

This program

That connection leads us to Incompleteness. If we know that there must be mathematical statements that are undecidable (like statements that are true but cannot be proved), we know that there are undecidable properties of computer programs. And if we know that there are undecidable properties of computer programs (like whether they halt), we know that there are undecidable statements in mathematics.

I find that deeply, deeply interesting.

This was provoked by an example from the Qi language manual. It came at a good time: after writing about various aspects of our industry and its limitations, I needed to be reminded how how much I enjoy thinking about programs.

Which brings me back around to the title. Computer Science is a big field. Programming is a big field. Working for a living developing software is a big field. I believe you have to pick and choose, you can’t learn everything, you can’t try to pick up every new thing that comes along.

But I believe that if you follow Morris’ dictum, you will be effective and also deeply engaged. Do not settle for mediocre ideas. Accept only those things that are useful, beautiful, or both. Do not settle for just beautiful or just useful. It is surprising how often useful things help you build beauty, and likewise how often beautiful things turn out to be useful in a different context.

Tyops, both on the same sentence:

"For example, we have proven that w can neither prove nor disprove Cantorâ€™s Continuum Hypothesis: it appears that within Number Theory, there is now way to know whether there exist infinities larger than Aleph Zero and smaller than Aleph One."

s,w,we,

s,now way,no way,

"For example, we have proven that w can neither prove nor disprove Cantorâ€™s Continuum Hypothesis: it appears that within Number Theory, there is now way to know whether there exist infinities larger than Aleph Zero and smaller than Aleph One."

s,w,we,

s,now way,no way,

Hi Reg,

unfortunately nobody will ever be able to win a Nobel Prize in Mathematics:

Why is there no Nobel Prize in Mathematics?

:-)

unfortunately nobody will ever be able to win a Nobel Prize in Mathematics:

Why is there no Nobel Prize in Mathematics?

:-)

Too bad, thanks for the link.

I think you're missing a point - the halting problem talks about "any machine" and "any input".

There can be a machine that decides for a particular machine and a particular input (there can be two such machines/outputs - one that says "true" and one that says "false". One of them is the correct answer)

There can be a machine that decides for a particular machine and a particular input (there can be two such machines/outputs - one that says "true" and one that says "false". One of them is the correct answer)

gg:

I don't understand what you're saying. Trivially, you can build two machines, one of which always says "halts" and the other of which always says "does not halt."

But if we don't know which machine is right, we have an undecidable problem.

How does that conflict with what I've written here? Can you expand on your point a bit??

I don't understand what you're saying. Trivially, you can build two machines, one of which always says "halts" and the other of which always says "does not halt."

But if we don't know which machine is right, we have an undecidable problem.

How does that conflict with what I've written here? Can you expand on your point a bit??

exactly - you have two machines and the halting problem is about whether a machine "exists". So for the simple case of a particular machine and a particular input it is obvious (as you wrote) that there *exists* a Turing machine that "returns" the correct answer.

The same is with the twin primes problem - since we don't know whether the theorem is right or wrong, we don't know if the Turing machine that tries to find a counterexample will stop or not. But we *do know* that it will be one of these options.

So for the twin primes problem, there *exists* a turing machine that outputs the correct answer ("halts"/"does not halt"). It is our problem that we don't know which one of them is correct.

The halting problem is about existence and not about correctness . So whether a given problem is unsolved in mathematics does not mean that there is no Turing machine that can decide it.

Of course (as the halting problem states) there is no Turing machine that can output a correct answers for *all* possible problem/input pairs.

(sorry for the bad English...)

The same is with the twin primes problem - since we don't know whether the theorem is right or wrong, we don't know if the Turing machine that tries to find a counterexample will stop or not. But we *do know* that it will be one of these options.

So for the twin primes problem, there *exists* a turing machine that outputs the correct answer ("halts"/"does not halt"). It is our problem that we don't know which one of them is correct.

The halting problem is about existence and not about correctness . So whether a given problem is unsolved in mathematics does not mean that there is no Turing machine that can decide it.

Of course (as the halting problem states) there is no Turing machine that can output a correct answers for *all* possible problem/input pairs.

(sorry for the bad English...)

GG:

I think there may be a communication gap. I think we both agree that there is no machine that answers whether*any* machine with *any*input halts.

I quoted Wikipedia saying: "there is no computable function that correctly determines which programs halt and which ones do not."

This talks about*one function* that can correctly answer whether *every* machine halts for *every* input.

So the existance of trivial machines or machines that correctly decide the halting behaviour of sets of machines does not invalidate the Halting Problem.

If even*one* machine exists and we cannot decide whether it halts or not, this proves the Halting Problem.

I think there may be a communication gap. I think we both agree that there is no machine that answers whether

I quoted Wikipedia saying: "there is no computable function that correctly determines which programs halt and which ones do not."

This talks about

So the existance of trivial machines or machines that correctly decide the halting behaviour of sets of machines does not invalidate the Halting Problem.

If even

Take this xkcd comic:

http://xkcd.com/167/

and replace the first bubble with "The tech industry sucks" and the last bubble with "Hey! I found String#to_proc!"

http://xkcd.com/167/

and replace the first bubble with "The tech industry sucks" and the last bubble with "Hey! I found String#to_proc!"

Maybe there was some misunderstanding (that's the problem with having English as a third language). My point was that giving the "twin primes" (or any other particular problem) as an example is not a supporting argument or explanation to the validity of the halting problem.

Anyway - we apparently agree on the facts :)

Anyway - we apparently agree on the facts :)

Ah, thank you so much for finding Qi! It looks like a possible gem.

I'm a bit tired of CL's all-encompassing design, Qi is much clearer.

Spent all night reading his book.

I'm a bit tired of CL's all-encompassing design, Qi is much clearer.

Spent all night reading his book.

I believe the conjecture requires the terms "all programs" and "all inputs".

For example, if a program has no inputs, we can sometimes determine if it will indeed run forever. That is, if its machine state at any given instance is identical to a previously seen state.. then it will run forever.

For example, if a program has no inputs, we can sometimes determine if it will indeed run forever. That is, if its machine state at any given instance is identical to a previously seen state.. then it will run forever.

Reg - you may have already read this but for anyone else in the comments looking to learn more...

A great and beautiful book which explores these topics is GEB (Godel, Escher, Bach).

A great and beautiful book which explores these topics is GEB (Godel, Escher, Bach).

Heh. Proof by nonexistent award:

"The Halting Problem is unsolvable. Proof: If you could solve it, you'd win the Nobel Prize in Mathematics. But there is no Nobel Prize in Mathematics; Q.E.D." ;)

(Yes, the HP is indeed undecidable. I was just amused by your discussion technique.)

Besides GEB, most of Raymond Smullyan's books also deal with the Halting Problem at some point, although Smullyan is much more taken with Godel's Incompleteness Theorem.

"The Halting Problem is unsolvable. Proof: If you could solve it, you'd win the Nobel Prize in Mathematics. But there is no Nobel Prize in Mathematics; Q.E.D." ;)

(Yes, the HP is indeed undecidable. I was just amused by your discussion technique.)

Besides GEB, most of Raymond Smullyan's books also deal with the Halting Problem at some point, although Smullyan is much more taken with Godel's Incompleteness Theorem.

Hilarious! That isn’t even

As you can tell, I’m a big Smullyan fan. I don not think it’s a coïncidence that he has written about Incompleteness and HP, for the reason I give above: they are deeply related.

<< Home

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 /