In the next five minutes you will learn— 1) What is the halting problem and why it is important 2) Some examples of halting and non-halting programs 3) Alan Turing's formal proof
Often, computers hang...
Progress bars stop or go backwards...
Or you get the dreaded spinning beach ball of death. ☠️
Does this mean that some programmer just get sloppy somewhere, or is it an unavoidable fact of life?
Actually, according to computer science, this is just life!
And that’s because fundamentally—for an arbitrary program—there’s no way to predict how long a program will take to run without running it.
This was proven by the mathematician Alan Turing in 1936.
Now, you're probably thinking, if I have a simple program like this:
def table(a, b):
for i in range(1, a):
for j in range(1, b):
print(i, j)
Of course I can calculate how long it takes to run.
(A iterations x B iterations = A x B print statements)
But that required us reading the code of the program and visualizing the possible paths through the program.
(This is called static analysis, by the way—analyzing a program without actually running it.)
And as a program becomes more complex, this becomes increasingly painful to do. And actually, there's no general way to do this for any program.
This is where the halting problem comes in.
Formulated by Turing, the problem asks:
Given a program and an input, can we determine if the program will eventually halt (finish running) or if it will run forever?
Let’s look at one more slightly better example before trying to solve the halting problem:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
This program will halt if n is a non-negative integer. Otherwise, it will run forever!
We figured this out because we are smart human beings, who can read the code and work backwards.
But now, look at Alan Turing's challenge—Can we write a computer program that will figure this out for us, regardless of the program?
Spoiler alert: No program can do this.
And this is what he said: If it were possible, that means you should be able to make a program like this:
def will_halt(program):
if blah blah blah:
return true
else:
return false
Which can clearly never be written!
To see why, we can write another mischievous program:
def tricky_program():
if will_halt(tricky_program):
while True:
pass
else:
return
This program references the will_halt program to check what will_halt expects it to do, and does the opposite.
Wait, the program passed to will_halt can also use will_halt itself? Isn’t that cheating?
Well no—if the program will_halt can be written, then then there's no reason the same logic couldn’t be used within tricky_program. It's just code.
While this may seem like a depressing outcome for software development everywhere, this is actually just the beginning of what makes computer programming a lot of fun. Just ask Alan Turing—he was having fun with this 40 years before the first personal computer was invented!
P.S. Of course, in the year 2024, you certainly have one thought after reading this. "OK, so we can't write a program that solves the halting problem, but we can train an AI to do it!" Well, the answer is still technically no, but that's a post for another day...
Top comments (0)