gimpert.com

Alan Turing Snippets
(mostly paraphrased from the Alan Turing Home Page)

His work introduced a concept of immense practical significance: the idea of the Universal Turing Machine. The concept of 'the Turing machine' is like that of 'the formula' or 'the equation'; there is an infinity of possible Turing machines, each corresponding to a different 'definite method' or algorithm. But imagine, as Turing did, each particular algorithm written out as a set of instructions in a standard form. Then the work of interpreting the instructions and carrying them out is itself a mechanical process, and so can itself be embodied in a particular Turing machine, namely the Universal Turing machine. A Universal Turing machine can be made do what any other particular Turing machine would do, by supplying it with the standard form describing that Turing machine. One machine, for all possible tasks.

Any Turing machine can be so encoded in a finite string of symbols. {A...Z, AA...AZ, BA...BZ, CA...} There are only a countable infinity of such encodings, hence only a countable number of Turing machines, hence only a countable number of solutions to computable problems. However, it can also be shown that there are a larger than countable number of possible problems for which there are no computable solutions.

Cantor's diagonalization argument is one of the triumphs of mathematical ingenuity. It proves that no one-to-one correspondence exists between the natural numbers and the set of all real numbers between zero and 1, inclusive; it is loosely equivalent to say that the infinite set of all real numbers is “bigger” than the infinite set of all natural numbers. The proof is by contradiction, and proceeds as follows:

First suppose that such a correspondence does exist; we can then say that some correspondence f maps a natural number n to the real number f(n) between zero and 1 with which n is paired. Now make a listing of the correspondences:

f(1) = 0. A[1,1] A[1,2] A[1,3]... f(2) = 0. A[2,1] A[2,2] A[2,3]... f(n) = 0. A[n,1] A[n,2] A[n,3]...

A[n,i] represents the ith digit of the real number associated with the natural number n. Define another real number

x = 0. B[1] B[2] B[j]...

Where B[j] = 1 unless A[j,j] = 1 in which case B[j] = 2. This is why it is called Cantor's diagonalization argument; you're changing the digits that lie on the diagonal between A[1,1] and A[n,n]. By doing so, you've guaranteed that x, a perfectly valid real number between zero and 1, is not included in the listing, because it differs in the nth decimal place from the real number paired with any natural number n. Since no one-to-one correspondence f can pair x with a natural number, no one-to-one correspondence between the natural numbers and the set of all real numbers between zero and 1 exists, Q.E.D.

Additionally, the abstract Universal Turing Machine naturally exploits what was later seen as the 'stored program' concept essential to the modern computer: it embodies the crucial twentieth-century insight that symbols representing instructions are no different in kind from symbols representing numbers. But computers, in this modern sense, did not exist in 1936. Turing created these concepts out of his mathematical imagination. Only nine years later would electronic technology be tried and tested sufficiently to make it practical to transfer the logic of his ideas into actual engineering.

Out of all the phenomena of life he fixed on the way asymmetry can arise out of initially symmetric conditions as first thing requiring explanation, and his answer, given without apparent reference to anyone else's work, was that it could arise from the nonlinearity of the chemical equations of reaction and diffusion. He modelled hypothetical chemical reactions on the circle and the plane, and for the repetitive numerical simulation required to test his ideas, became the first serious user of an electronic computer for mathematical research.

But since 1948, the conditions of the Cold War, and the [United Kingdom's] alliance with the United States, meant that known homosexuals had become ineligible for security clearance. Rather than go to prison he accepted, for the period of a year, injections of oestrogen intended to neutralise his libido. He was found by his cleaner when she came in on 8 June 1954. He had died the day before of cyanide poisoning, a half-eaten apple beside his bed. His mother believed he had accidentally ingested cyanide from his fingers after an amateur chemistry experiment, but it is more credible that he had successfully contrived his death to allow her alone to believe this. The coroner's verdict was suicide.