 index be n, and call T(n) the TM that uses this program. We now have an infinite catalog of TM, which can be listed as T(1), T(2), T(3), Consider next the input data on the TM tape. The data also form a string of finite size, which corresponds to any binary number. Likewise, we can index and order these data into a list, forming the infinite, but countable, set of all possible input data strings, with p as the index. Call T(n, p) the unique Turing machine T(n), which has the data string p on its input tape. If T(n, p) halts, call the output data T* (n, p). The halting problem is summarized by the question: "Given a Turing machine T(n, p), is there any rule to determine whether it will halt?" With the previous definitions, we can now prove the undecidability of the halting problem. I shall do this by assuming that such a rule (call it the halting rule) does exist; then I will show that this assumption leads to an intractable contradiction! With the halting rule, we know for sure whether or not a given machine T(n,p) does halt. In all the favorable cases (halting TMs), we can safely run the computa- tions to a conclusion, and tabulate the output data T*(n,p). We can, thus, fill in a two-dimensional array of (n, p) such as that in Table 7.7. In the unfavorable cases (nonhalting TMs), there is no point in running the machines, since the halting rule tells us that they never halt. In this case, we just enter a X mark in the corresponding array cell. This array is infinite in two dimensions, SO it can never be physically com- pleted, but this does not matter for the demonstration. The halting rule yields a Boolean answer to the statement "T(n, p) halts," under the form q = true or q = false. We can, therefore, design another universal Turing machine H(t) with a program t that does the following: In the favorable case (q = true), emulate T(p, p) to compute the output is then (p, p) + 1 (to differentiate from the output of machine T(p, p)). In the unfavorable case (q = false), skip calculation and output 0. 10 See http: