raganwald
(This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)

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

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.
Wikipedia

(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:

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

  2. 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.

  3. 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

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.
Wikipedia


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.

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 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.
 

Comments on “Have nothing in your house that you do not know to be useful, or believe to be beautiful:
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,
 
Thanks!!!
 
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

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)
 
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??
 
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...)
 
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 anyinput 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.
 
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!"
 
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 :)
 
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 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.
 
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).
 
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.
 
Proof by nonexistent award

Hilarious! That isn’t even close to what I meant, but it is easily the funniest comment I’ve read today, thank you.

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
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 /