Prerequisites
 You must be able to understand basic programming constructs.
 Having a working knowledge of the Ruby programming language would be useful.
Video Explanation
Questions
 Who proved that the halting problem was impossible to solve, and when?
 Is it possible to create a program that will tell us whether a given program will halt or not?

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 < 0) f2(n + 2) elsif (n > 0) f2(n  2) end end def f3 (n) if (n < 2) return n else return f3(n1) + f3(n2) 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(m1, 1) else return f4(m1, f4(m, n1)) end end

Given the function
f4
above, what do you notice about the number of steps it takes to run the function asm
increases? Does this make it difficult to find out whether it halts or not?  Given that it is impossible to find out in a general case whether a program will halt or not, is it possible to find out whether a program halts in a specific case? Consider the following scenarios: programs that contain no loops, programs that contain no recursion, programs that contain no decisions.
 Debate with your partner or class, whether this result reduces the usefulness of computers.
 A turingcomplete computer is one that can express any computable algorithm  that is, "when the rules followed in sequence on arbitrary data can produce the result of any calculation". Is it possible that there is a broader definition for this "universal computer" which would allow us to solve the halting problem, and if so, what form would it take?
 Give a simple example of a computer program that halts, and a computer program that doesn't halt. Extra points if you can make something that looks like it should halt, but doesn't and likewise, something that looks like it won't halt, but does.