# The Halting Problem

The halting problem is an important theory in computer science. It gives us tools to explains the fundamental limitations of computers: what kind of problems can we solve with computers? What problems are impossible?

## Pre-requisites

1. You must be able to understand basic programming constructs.
2. Having a working knowledge of the Ruby programming language would be useful.

## Questions

1. Who proved that the halting problem was impossible to solve, and when?
2. Is it possible to create a program that will tell us whether a given program will halt or not?
3. Classify the following examples into halts and doesn't halt. Trace the programs with the inputs given.
``````#!/usr/bin/env ruby

def f1

end

def f2 (n)
if (n &lt; 0)
f2(n + 2)
elsif (n &gt; 0)
f2(n - 2)
end
end

def f3 (n)
if (n &lt; 2)
return n
else
return f3(n-1) + f3(n-2)
end
end

# This one is complicated - don't try it for m or n greater than 2. If you can't figure it out - don't worry !
def f4 (m,n)
if (m == 0)
return n+1
elsif n == 0
return f4(m-1, 1)
else
return f4(m-1, f4(m, n-1))
end
end
``````
4. Given the function `f4` above, what do you notice about the number of steps it takes to run the function as `m` increases? Does this make it difficult to find out whether it halts or not?