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.

(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

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.

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.  ¶ 2:43 PM