Halting Problem

This post is also available in: Spanish

Halting Problem

The halting problem was first suggested by Turing at the beginning of the 20th century. It deals with computer programs and finding out whether they will or not stop.

For example, let’s take a computer program that computes 2 + 2. We know the program will stop when it gives us the output “4”. We could now make a program that tried to find the largest possible natural number and sopped when it did. Since natural numbers are infinite, we know that program will never stop.

We could now make another program which went through every single even number and checked whether it can be expressed as the sum of two primes, and finally stopped when it found one that can’t. In this case, we have no way of knowing whether the program will ever stop, since doing so would entail having a proof of Goldbach’s conjecture, which we don’t.

Turing challenged himself to find an algorithm which could be used to find out whether any program will eventually halt: then he proved it is impossible to do so. There cannot be any general-purpose algorithm to find out whether a program will stop or not. This result is closely related to Gödel’s incompleteness theorem and can be seen as another way of looking at the same idea.

For more information, see the Wikipedia.

Share and Enjoy:
  • Digg
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Bitacoras.com
  • Google Buzz
  • Meneame
  • Reddit
  • RSS

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>