computability roughly, the possibility of computation on a Turing machine. The first convincing general definition, A. N. Turing’s (1936), has been proved equivalent to the known plausible alternatives, so that the concept of computability is generally recognized as an absolute one. Turing’s definition referred to computations by imaginary tape-processing machines that we now know to be capable of computing the same functions (whether simple sums and products or highly complex, esoteric functions) that modern digital computing machines could compute if provided with sufficient storage capacity. In the form ‘Any function that is computable at all is computable on a Turing machine’, this absoluteness claim is called Turing’s thesis. A comparable claim for Alonzo Church’s (1935) concept of lcomputability is called Church’s thesis. Similar theses are enunciated for Markov algorithms, for S. C. Kleene’s notion of general recursiveness, etc. It has been proved that the same functions are computable in all of these ways. There is no hope of proving any of those theses, for such a proof would require a definition of ‘computable’ – a definition that would simply be a further item in the list, the subject of a further thesis. But since computations of new kinds might be recognizable as genuine in particular cases, Turing’s thesis and its equivalents, if false, might be decisively refuted by discovery of a particular function, a way of computing it, and a proof that no Turing machine can compute it. The halting problem for (say) Turing machines is the problem of devising a Turing machine that computes the function h(m, n) % 1 or 0 depending on whether or not Turing machine number m ever halts, once started with the number n on its tape. This problem is unsolvable, for a machine that computed h could be modified to compute a function g(n), which is undefined (the machine goes into an endless loop) when h(n, n) % 1, and otherwise agrees with h(n, n). But this modified machine – Turing machine number k, say – would have contradictory properties: started with k on its tape, it would eventually halt if and only if it does not. Turing proved unsolvability of the decision problem for logic (the problem of devising a Turing machine that, applied to argument number n in logical notation, correctly classifies it as valid or invalid) by reducing the halting problem to the decision problem, i.e., showing how any solution to the latter could be used to solve the former problem, which we know to be unsolvable. See also CHURCH’S THESIS, COMPUTER THE- ORY, TURING MACHIN. R.J.