*all*possible program-input pairs CANNOT exist. There are no way of computing these functions. At first I was stubborn and had a hard time believing this is true when computers didn’t exist when Turing’s proof was deduced. Then I decided look into it further and I discovered

*Gödel’s incompleteness theorems (Which basically is a theorem concerning the limits of provability in formal logical axioms in terms of number theory also take into*which helped me understand some background knowledge, but I was still on the edge of full believing the halting problem is non computable. After thinking about it for days it finally became more clear as to the conclusion.

*undecidable propositions*into account)Now you might be thinking what about Artificial Intelligence, Watson for example; can’t these super computers solve problem such as the halting problem? Well some people are concerned that we are on the road to technological singularity in the computer world, but lets just have some faith Turing’s Disproof to the Halting problem is strong enough to prevent skynet from ever happening haha!

**Computability Terminology :**

Definition 1: Let f:I→O be a function. Then f is **well-defined** ⟺ for each x∈I, there is a unique y∈O such that f(x)=y.

Let g,h:I→O be well-defined functions (computable)

Then g is **computable** ⟺ there is a program P such that ∀x∈I, g(x)=P(x).

**Reductions:** Then g **reduces** to h ⟺ g can be implemented with h.

My Professor showed us a proof technique in order to prove a function computable then all we have to do is that that function reduces to a computable function, vice versa.

At the current state of affairs, AI isn’t really the type of thing that would solve these types of issues. Watson is much more valuable for ‘text-data mining’, stuff that normal computers wouldn’t handle very well—check out the Watson-based course at UofT: http://www.cs.utoronto.ca/~sengels/csc490

Another thing I’d suggest, if you’re interested in all this Turing/Gödel/logic stuff, is Gödel, Escher, Bach by Hofstadter (http://en.wikipedia.org/wiki/Gödel,_Escher,_Bach). Long read, but very worth it. It’s winter break after all 🙂