//pass.maths.org.uk/issue5/turing/, and also http://en.wikipedia.org/wiki/Halting_problem. Integers are countable, because given any two integer bounds (n1, N2 > n1), there exists a finite number 1 of integers between the two bounds. Algorithmic entropy and Kolmogorov complexity Table 7.7 Array representing the infinite sets of Turing machines T(n) having p for input data, with examples of corresponding output data T* (n, p) returned when the machine T(n, p) halts, expressed as decimal numbers. The arrangements known by the rule not to halt are indicated with a cross. The bottom row defines a hypothetical machine H(t), which always halts, returns T*(p,p) + 1 if T(p) halts and 0 otherwise. T*(p,p) + 1 or 0 The various outputs of H(t), based on the values of T (p, p), are shown in the bottom row of Table 7.7. The new TM H(t), thus, always halts, since in either case (q = true or q = false), and over the infinite set of possible input data p, it has a definite output. We have, thus, identified a TM that always halts, regardless of the input. Since it is a TM, it should appear somewhere in the array. But H(t) is nowhere to be found. Indeed, the machine H(t,t) has an output H*(t,t), which, by definition, is different from the outputs T*(t,t) of any known machines T(t,t). The paradox can be summarized as follows: If a halting rule existed for any Turing machine, one could build another Turing machine that always halts for any possible input. But such a machine appears nowhere in the infinite list of possible Turing machines. It can be concluded, therefore, (but only as a proof sketch) that, in the general case, the halting rule does not exist, and that the halting problem is generally undecidable. The fact that there is no solution to the halting problem in the general case does not preclude an intuitive, if not formal solution in any given particular case. It is trivial, indeed, to define Turing machines that for any data input (a) either certainly halt or (b) certainly never halt. 12 At this point, we shall leave the