Turings Halting Theorem

The halting problem thus asks whether it is possible to tell in advance if a general program will halt its execution or, put another way, whether an arbitrary program s 

In a landmark 1936 paper, Turing proved that no such program Vn exists [tur-ing36]-. given an arbitrary program V and input data P, it is in general impossible to predict before-liand whether, or when, V will ever finish processing V. 

We give a brief sketch of Turing s proof below. It is essentially a proof-bycontradiction, showing that if an infallible halting-checker program Vn is assumed to exist, a computation can always be found such that it runs forever if Vh says it halts, and halts if Vi says it does not. 

Assuming that such a halting-checker program Vn in fact exists, we can use it to construct another program, V, that uses programs as data inputs, and reverses the roles of its yes / no responses  

---

Are there any noncomputable numbers They are certain to exist since the cardinality of the set of all possible programs (which is equal to that of the integers) is less than the cardinality of the set of reals. It is, in fact, easy to construct a noncomputable number, using Turing s Halting Theorem number, in some arbitrary manner, all possible programs that run with, say, a single input instruction Pi (-> l,p2 2,...,pn n,..., and set ( = n2, where q = 1 if the... 

---