艾伦·图灵Alan Turing

艾伦·图灵出生在伦敦帕丁顿。他的父亲朱利叶斯·马西森图灵是印度公务员系统中的英国成员，经常在国外。图灵的母亲埃塞尔·萨拉·斯托尼是马德拉斯铁路总工程师的女儿，图灵的父母在印度相识并结婚。当图灵大约一岁时，他的母亲回到印度与丈夫团聚，把图灵留在英格兰与家庭朋友在一起。图灵被送到学校，但似乎没有获得任何益处，因此几个月后他被从学校接走。

接着他被送到Hazlehurst预备学校，在那里他在大多数科目上似乎是一个“中等偏上”的学生，但非常热衷于追随自己的想法。在这所学校期间，他对国际象棋产生了兴趣，还加入了辩论社。他于1926年完成了普通入学考试，然后进入Sherborne学校。1926年正是大罢工的一年，当罢工进行时，图灵从家骑自行车60英里去学校，这对后来成为几乎达到奥林匹克标准的优秀运动员的图灵来说并不是太艰巨的任务。他发现很难适应这所公学的期望，然而他的母亲却如此坚决地认为他应该接受公学教育。许多最具独创性的思想家都发现传统学校教育是一个几乎无法理解的过程，图灵的情况似乎也是如此。他的天才驱使他走自己的方向，而不是老师要求的方向。

他因笔迹受到批评，英语学得很吃力，甚至在数学上他也过于关注自己的想法，而不愿用老师教的方法来解题。尽管给出了非传统的答案，图灵在Sherborne期间还是赢得了几乎每一个可能的数学奖项。在化学这门他从小就感兴趣的学科中，他按照自己的计划进行实验，这让他的老师很不高兴。图灵的校长写道（例如见[6]）：-

如果他要留在公学，就必须以接受教育为目标。如果他只想成为一名科学专家，那他在公学就是在浪费时间。

这更多地说明了图灵所接受的学校制度的问题，而不是图灵本人的问题。然而，图灵在学校期间学习了深刻的数学，尽管他的老师们可能并不知道他在独自进行的研究。他读了阿尔伯特·爱因斯坦关于相对论的论文，还读了亚瑟·爱丁顿的The nature of the physical world中关于量子力学的内容。

1928年发生了一件对图灵一生产生重大影响的事。他与克里斯托弗·莫科姆（Christopher Morcom）建立了亲密的友谊，莫科姆是比他高一年级的学生，两人一起研究科学思想。也许图灵第一次找到了一个可以分享自己思想和想法的人。然而莫科姆于1930年2月去世，这一经历对图灵是毁灭性的打击。他在莫科姆发病的那一刻就有一种莫科姆将死的预感，并觉得这是科学无法解释的事情。他后来写道（例如见[6]）：-

要解释掉这些事情并不困难——但是，我怀疑！

尽管学校岁月艰难，图灵还是于1931年进入剑桥大学国王学院学习数学。这并非没有困难。图灵在1929年参加了奖学金考试，获得了一项助学金，但不是奖学金。他对这一成绩不满意，第二年再次参加考试，这次获得了奖学金。在许多方面，剑桥对于像图灵这样不循规蹈矩的人来说，比学校要容易得多。他现在更能探索自己的想法，并在1933年读了伯特兰·罗素的Introduction to mathematical philosophy。大约在同一时间，他读了冯·诺伊曼1932年关于量子力学的教科书，这个主题他一生中多次回到。

1933年，图灵开始对数学逻辑产生兴趣。那年12月，他在剑桥道德科学俱乐部宣读了一篇论文，记录如下（例如见[6]）：-

图灵宣读了一篇关于“数学与逻辑”的论文。他提出，纯粹逻辑主义的数学观是不充分的；数学命题拥有多种解释，而逻辑主义只是其中一种。

当然，1933年也是希特勒在德国崛起以及英国反战运动兴起的一年。图灵加入了反战运动，但他并没有像许多人那样转向马克思主义或和平主义。

图灵于1934年毕业，随后在1935年春天，他参加了马克斯·纽曼关于数学基础的高级课程。这门课程研究了库尔特·弗雷德里希·哥德尔的不完备性结果和大卫·希尔伯特关于可判定性的问题。从某种意义上说，‘可判定性’是一个简单的问题，即给定一个数学命题，能否找到一个算法来决定该命题是真还是假。对于许多命题，找到这样的算法很容易。真正的困难在于证明对于某些命题不存在这样的算法。当给出一个算法来解决问题时，很清楚它确实是一个算法，然而却没有一个足够严格的算法定义，使得人们能够证明不存在任何算法。图灵开始研究这些想法。

图灵于1935年因学位论文On the Gaussian error function当选为剑桥大学国王学院会士，该论文证明了关于概率论的基本结果，即central limit theorem。尽管中心极限定理最近才被发现，图灵对此并不知晓，并独立发现了它。1936年，图灵获得了史密斯奖。

图灵在剑桥的成就归功于他在概率论方面的工作。然而，自从参加马克斯·纽曼的课程以来，他一直在研究可判定性问题。1936年，他发表了On Computable Numbers, with an application to the Entscheidungsproblem。正是在这篇论文中，图灵引入了一种抽象机器，现在称为“图灵机”，它使用一套精确的有限规则（由有限表给出）从一个状态移动到另一个状态，并取决于它从纸带上读取的单个符号。

图灵机器可以在纸带上写一个符号，或从纸带上删除一个符号。图灵写道[13]：-

写下的某些符号将构成数字序列，即正在计算的实数的十进制表示。其他符号只是“辅助记忆”的粗略笔记。只有这些粗略笔记才可能被擦除。

他将可计算数定义为十进制展开可以由图灵机器从空白纸带开始产生的实数。他证明了π是可计算的，但由于只有可数个实数是可计算的，大多数实数不可计算。然后他描述了一个不可计算的数，并指出这似乎是一个悖论，因为他似乎用有限术语描述了一个不能用有限术语描述的数。然而，图灵理解了这一表面悖论的根源。不可能（用另一台图灵机器）判定一台具有给定指令表的图灵机器是否会输出无限的数字序列。

尽管这篇论文包含的思想自发表以来对数学和计算机科学具有根本的重要性，但要在Proceedings of the London Mathematical Society上发表它并不容易。原因是丘奇于1936年在American Journal of Mathematics上发表了An unsolvable problem in elementary 数论，该文也证明了算术不存在判定程序。图灵的方法与丘奇的方法非常不同，但马克斯·纽曼必须在伦敦数学会同意发表图灵的论文之前为其辩护。图灵修订后的论文引用了丘奇的结果，该论文于1936年4月首次完成，1936年8月以这种方式修订，并于1937年付印。

与丘奇讨论的一个良好结果是，图灵于1936年成为普林斯顿大学的研究生。在普林斯顿，图灵在丘奇的指导下进行研究，并于1938年返回英国，此前他在1937年暑假回到英国时第一次遇到了路德维希·维特根斯坦。他在普林斯顿工作期间的主要出版物是Systems of Logic Based on Ordinals，于1939年出版。马克斯·纽曼在[13]中写道：-

这篇论文充满了有趣的建议和想法。……[它]对图灵关于直觉在数学证明中地位的观点有很大启发。

在这篇论文发表之前，图灵发表了两篇关于更为传统数学主题的论文。其中一篇讨论了用有限群逼近李群的方法。另一篇论文证明了关于群扩张的结果，这些结果最初由Reinhold Baer证明，给出了更简单、更统一的方法。

也许图灵在图灵机方面工作最显著的特点是，他在技术尚未达到可以实际建造的程度之前就描述了一台现代计算机。他在1936年的论文中证明了通用图灵机的存在[13]：-

……这种机器可以完成任何专用机器的工作，也就是说，只要插入一条带有合适“指令”的纸带，它就能执行任何计算任务。

尽管对图灵来说，“计算机”是进行计算的人，但我们必须在他对通用图灵机的描述中看到我们今天所认为的、以纸带作为程序的计算机。

在普林斯顿时，图灵曾考虑过建造计算机的想法。1938年回到剑桥后，他开始建造一台模拟机械装置来研究黎曼假设，今天许多人认为这是数学中最大的未解决问题。然而，他的工作很快呈现出新的面貌，因为他返回后不久就联系了政府密码学校，后者请他帮助破译德国Enigma密码。

1939年宣战时，图灵立即转到布莱切利园的政府密码学校全职工作。尽管在布莱切利园进行的工作受《官方保密法》约束，但许多内容最近已成为公开知识。图灵在破译密码以及开发计算机来协助破译方面的卓越想法，可能在战争期间比任何其他人都拯救了更多军事人员的生命。对他来说，这也是一段快乐的时光[13]：-

……也许是他一生中最幸福的时期，他的创造力得到了充分发挥，有温和的日常安排来塑造每一天，还有一群志同道合的同事。

与另一位数学家 W G 戈登·维尔赫曼 一起，图灵 在波兰数学家早期工作的基础上开发了 Bombe，这台机器从 1940 年末开始破译德国空军 Enigma 机发送的所有信息。德国海军的 Enigma 机要难破译得多，但这正是 图灵 喜欢的那种挑战。到 1941 年中期，图灵 的统计方法连同截获的信息，使德国海军的信号在布莱切利被破译。

从1942年11月到1943年3月，图灵在美国就破译问题和语音保密系统进行联络。德国人编码信息方式的改变意味着布莱切利园失去了破译信息的能力。图灵没有直接参与成功破译这些更复杂的密码，但他的思想在这项工作中被证明极为重要。图灵于1945年因对战争努力的重大贡献而被授予O.B.E.。

战争结束时，图灵 应伦敦国家物理实验室之邀设计一台计算机。他提议自动计算引擎（ACE）的报告于1946年3月提交。图灵 的设计在当时是一份原创性的详细设计，也是现代意义上计算机的构想书。他为 ACE 规划的存储容量，被大多数看过报告的人认为过于雄心勃勃，几乎不可能实现，项目批准也因此被拖延。

图灵 于1947-48学年回到剑桥，他的兴趣广泛涉及许多远离计算机或数学的课题；尤其研究了神经学和生理学。不过，在此期间他并未忘记计算机，还为计算机编写了编程代码。他在学术圈外也有兴趣，战后认真投入了田径运动。他是 欧内斯特·沃尔顿 田径俱乐部的成员，以创纪录的成绩赢得了他们的3英里和10英里冠军。他参加了1947年的A.A.A.马拉松赛，获得第五名。

到 1948 年，马克斯·纽曼 是曼彻斯特大学的数学教授，他邀请 图灵 去那里担任高级讲师。图灵 从国家物理实验室辞职，前往曼彻斯特任职。马克斯·纽曼 在 [13] 中写道，在曼彻斯特：-

……F C Williams 和 T Kilburn 开始建造一台计算机。预期 图灵 将领导这项工作的数学方面，并且有几年他继续工作，首先设计子程序，这类机器的较大程序就是由这些子程序构建的，然后，随着这类工作变得标准化，他转向数值分析中更一般的问题。

1950年，图灵在Mind上发表了Computing machinery and intelligence。这是他又一部非凡的著作，出自他那极具创造力的头脑，似乎预见到了随着计算机发展将会出现的问题。他研究的问题如今正处于人工智能的核心。正是在这篇1950年的论文中，他提出了图灵测试，时至今日，人们仍在试图回答计算机能否具有智能时应用这一测试[1]：-

……他开始参与关于机器与大脑之间差异与相似之处的讨论。图灵的观点以极大的力量和机智表达出来，即那些认为两者之间存在不可逾越的鸿沟的人应当指出差异究竟在哪里。

图灵没有忘记可判定性问题，这曾是他那些杰出数学出版物的起点。群的表现理论中的主要问题之一是：给定有限呈现群中的任意一个字，是否存在一种算法来判定该字是否等于单位元。波斯特已经证明对于半群不存在这样的算法。图灵起初以为他已经对群证明了同样的结果，但就在他为其证明举行讨论班之前，他发现了一个错误。他能够从有缺陷的证明中挽救出这样一个事实：存在一个具有不可解字问题的可消半群，并于1950年发表了这个结果。Boone利用图灵这篇论文中的思想，于1957年证明了一个具有不可解字问题的群的存在。

图灵 于1951年当选为 伦敦皇家学会 会士，主要因为他在1936年关于 图灵 机器的工作。到1951年，他正致力于将数学理论应用于生物形态。1952年，他发表了对形态发生——即生物体中模式和形态的发育——理论研究的第一部分。

1952年，图灵 因向警方报告一桩同性恋事件的细节，而因违反英国同性恋法规被捕。他去警察局是因为受到敲诈威胁。1952年3月31日，他作为同性恋者受审，除了表示自己看不出行为有何不妥外，没有作任何辩护。被判有罪后，他面临监禁或注射雌激素一年的选择。他接受了后者，随后又回到了广泛的学术追求中。

2009年9月10日，英国首相戈登·布朗代表英国政府，就战后 图灵 所受的对待，作出了正式的公开道歉。

他不仅推进了对形态发生的进一步研究，还致力于量子理论中的新思想、用旋量表示基本粒子以及相对论。尽管他对自己的性取向完全公开，但他还有另一种不幸，由于《官方保密法》他不得谈论此事。

布莱切利园的破译工作成为GCHQ新的破译和情报工作的基础。随着冷战，这成为一项重要行动，图灵继续为GCHQ工作，尽管他在曼彻斯特的同事对此完全不知情。在他被定罪后，他的安全许可被撤销。更糟糕的是，安全官员现在极其担心，一个完全了解GCHQ正在进行的工作的人现在被标记为安全风险。他有许多外国同事，任何学者都会如此，但警方开始调查他的外国访客。图灵在1953年在希腊度的一次假期引起了安全官员的恐慌。

图灵在进行电解实验时死于氰化钾中毒。在他身旁一个吃了一半的苹果上发现了氰化物。一项调查得出结论，这是自行服用的，但他的母亲始终坚称这是一次意外。

Alan Turing was born at Paddington, London. His father, Julius Mathison Turing, was a British member of the Indian Civil Service and he was often abroad. Alan's mother, Ethel Sara Stoney, was the daughter of the chief engineer of the Madras railways and Alan's parents had met and married in India. When Alan was about one year old his mother rejoined her husband in India, leaving Alan in England with friends of the family. Alan was sent to school but did not seem to be obtaining any benefit so he was removed from the school after a few months.

Next he was sent to Hazlehurst Preparatory School where he seemed to be an 'average to good' pupil in most subjects but was greatly taken up with following his own ideas. He became interested in chess while at this school and he also joined the debating society. He completed his Common Entrance Examination in 1926 and then went to Sherborne School. Now 1926 was the year of the general strike and when the strike was in progress Turing cycled 60 miles to the school from his home, not too demanding a task for Turing who later was to become a fine athlete of almost Olympic standard. He found it very difficult to fit into what was expected at this public school, yet his mother had been so determined that he should have a public school education. Many of the most original thinkers have found conventional schooling an almost incomprehensible process and this seems to have been the case for Turing. His genius drove him in his own directions rather than those required by his teachers.

He was criticised for his handwriting, struggled at English, and even in mathematics he was too interested with his own ideas to produce solutions to problems using the methods taught by his teachers. Despite producing unconventional answers, Turing did win almost every possible mathematics prize while at Sherborne. In chemistry, a subject which had interested him from a very early age, he carried out experiments following his own agenda which did not please his teacher. Turing's headmaster wrote (see for example [6]):-

If he is to stay at Public School, he must aim at becoming educated. If he is to be solely a Scientific Specialist, he is wasting his time at a Public School.

This says far more about the school system that Turing was being subjected to than it does about Turing himself. However, Turing learnt deep mathematics while at school, although his teachers were probably not aware of the studies he was making on his own. He read Einstein's papers on relativity and he also read about quantum mechanics in Eddington's The nature of the physical world.

An event which was to greatly affect Turing throughout his life took place in 1928. He formed a close friendship with Christopher Morcom, a pupil in the year above him at school, and the two worked together on scientific ideas. Perhaps for the first time Turing was able to find someone with whom he could share his thoughts and ideas. However Morcom died in February 1930 and the experience was a shattering one to Turing. He had a premonition of Morcom's death at the very instant that he was taken ill and felt that this was something beyond what science could explain. He wrote later (see for example [6]):-

It is not difficult to explain these things away - but, I wonder!

Despite the difficult school years, Turing entered King's College, Cambridge, in 1931 to study mathematics. This was not achieved without difficulty. Turing sat the scholarship examinations in 1929 and won an exhibition, but not a scholarship. Not satisfied with this performance, he took the examinations again in the following year, this time winning a scholarship. In many ways Cambridge was a much easier place for unconventional people like Turing than school had been. He was now much more able to explore his own ideas and he read Russell's Introduction to mathematical philosophy in 1933. At about the same time he read von Neumann's 1932 text on quantum mechanics, a subject he returned to a number of times throughout his life.

The year 1933 saw the beginnings of Turing's interest in mathematical logic. He read a paper to the Moral Science Club at Cambridge in December of that year of which the following minute was recorded (see for example [6]):-

A M Turing read a paper on "Mathematics and logic". He suggested that a purely logistic view of mathematics was inadequate; and that mathematical propositions possessed a variety of interpretations of which the logistic was merely one.

Of course 1933 was also the year of Hitler's rise in Germany and of an anti-war movement in Britain. Turing joined the anti-war movement but he did not drift towards Marxism, nor pacifism, as happened to many.

Turing graduated in 1934 then, in the spring of 1935, he attended Max Newman's advanced course on the foundations of mathematics. This course studied Gödel's incompleteness results and Hilbert's question on decidability. In one sense 'decidability' was a simple question, namely given a mathematical proposition could one find an algorithm which would decide if the proposition was true of false. For many propositions it was easy to find such an algorithm. The real difficulty arose in proving that for certain propositions no such algorithm existed. When given an algorithm to solve a problem it was clear that it was indeed an algorithm, yet there was no definition of an algorithm which was rigorous enough to allow one to prove that none existed. Turing began to work on these ideas.

Turing was elected a fellow of King's College, Cambridge, in 1935 for a dissertation On the Gaussian error function which proved fundamental results on probability theory, namely the central limit theorem. Although the central limit theorem had recently been discovered, Turing was not aware of this and discovered it independently. In 1936 Turing was a Smith's Prizeman.

Turing's achievements at Cambridge had been on account of his work in probability theory. However, he had been working on the decidability questions since attending Newman's course. In 1936 he published On Computable Numbers, with an application to the Entscheidungsproblem. It is in this paper that Turing introduced an abstract machine, now called a "Turing machine", which moved from one state to another using a precise finite set of rules (given by a finite table) and depending on a single symbol it read from a tape.

The Turing machine could write a symbol on the tape, or delete a symbol from the tape. Turing wrote [13]:-

Some of the symbols written down will form the sequences of figures which is the decimal of the real number which is being computed. The others are just rough notes to "assist the memory". It will only be these rough notes which will be liable to erasure.

He defined a computable number as real number whose decimal expansion could be produced by a Turing machine starting with a blank tape. He showed that π was computable, but since only countably many real numbers are computable, most real numbers are not computable. He then described a number which is not computable and remarks that this seems to be a paradox since he appears to have described in finite terms, a number which cannot be described in finite terms. However, Turing understood the source of the apparent paradox. It is impossible to decide (using another Turing machine) whether a Turing machine with a given table of instructions will output an infinite sequence of numbers.

Although this paper contains ideas which have proved of fundamental importance to mathematics and to computer science ever since it appeared, publishing it in the Proceedings of the London Mathematical Society did not prove easy. The reason was that Alonzo Church published An unsolvable problem in elementary number theory in the American Journal of Mathematics in 1936 which also proves that there is no decision procedure for arithmetic. Turing's approach is very different from that of Church but Newman had to argue the case for publication of Turing's paper before the London Mathematical Society would publish it. Turing's revised paper contains a reference to Church's results and the paper, first completed in April 1936, was revised in this way in August 1936 and it appeared in print in 1937.

A good feature of the resulting discussions with Church was that Turing became a graduate student at Princeton University in 1936. At Princeton, Turing undertook research under Church's supervision and he returned to England in 1938, having been back in England for the summer vacation in 1937 when he first met Wittgenstein. The major publication which came out of his work at Princeton was Systems of Logic Based on Ordinals which was published in 1939. Newman writes in [13]:-

This paper is full of interesting suggestions and ideas. ... [It] throws much light on Turing's views on the place of intuition in mathematical proof.

Before this paper appeared, Turing published two other papers on rather more conventional mathematical topics. One of these papers discussed methods of approximating Lie groups by finite groups. The other paper proves results on extensions of groups, which were first proved by Reinhold Baer, giving a simpler and more unified approach.

Perhaps the most remarkable feature of Turing's work on Turing machines was that he was describing a modern computer before technology had reached the point where construction was a realistic proposition. He had proved in his 1936 paper that a universal Turing machine existed [13]:-

... which can be made to do the work of any special-purpose machine, that is to say to carry out any piece of computing, if a tape bearing suitable "instructions" is inserted into it.

Although to Turing a "computer" was a person who carried out a computation, we must see in his description of a universal Turing machine what we today think of as a computer with the tape as the program.

While at Princeton Turing had played with the idea of constructing a computer. Once back at Cambridge in 1938 he starting to build an analogue mechanical device to investigate the Riemann hypothesis, which many consider today the biggest unsolved problem in mathematics. However, his work would soon take on a new aspect for he was contacted, soon after his return, by the Government Code and Cypher School who asked him to help them in their work on breaking the German Enigma codes.

When war was declared in 1939 Turing immediately moved to work full-time at the Government Code and Cypher School at Bletchley Park. Although the work carried out at Bletchley Park was covered by the Official Secrets Act, much has recently become public knowledge. Turing's brilliant ideas in solving codes, and developing computers to assist break them, may have saved more lives of military personnel in the course of the war than any other. It was also a happy time for him [13]:-

... perhaps the happiest of his life, with full scope for his inventiveness, a mild routine to shape the day, and a congenial set of fellow-workers.

Together with another mathematician W G Welchman, Turing developed the Bombe, a machine based on earlier work by Polish mathematicians, which from late 1940 was decoding all messages sent by the Enigma machines of the Luftwaffe. The Enigma machines of the German navy were much harder to break but this was the type of challenge which Turing enjoyed. By the middle of 1941 Turing's statistical approach, together with captured information, had led to the German navy signals being decoded at Bletchley.

From November 1942 until March 1943 Turing was in the United States liaising over decoding issues and also on a speech secrecy system. Changes in the way the Germans encoded their messages had meant that Bletchley lost the ability to decode the messages. Turing was not directly involved with the successful breaking of these more complex codes, but his ideas proved of the greatest importance in this work. Turing was awarded the O.B.E. in 1945 for his vital contribution to the war effort.

At the end of the war Turing was invited by the National Physical Laboratory in London to design a computer. His report proposing the Automatic Computing Engine (ACE) was submitted in March 1946. Turing's design was at that point an original detailed design and prospectus for a computer in the modern sense. The size of storage he planned for the ACE was regarded by most who considered the report as hopelessly over-ambitious and there were delays in the project being approved.

Turing returned to Cambridge for the academic year 1947-48 where his interests ranged over many topics far removed from computers or mathematics; in particular he studied neurology and physiology. He did not forget about computers during this period, however, and he wrote code for programming computers. He had interests outside the academic world too, having taken up athletics seriously after the end of the war. He was a member of Walton Athletic Club winning their 3 mile and 10 mile championship in record time. He ran in the A.A.A. Marathon in 1947 and was placed fifth.

By 1948 Newman was the professor of mathematics at the University of Manchester and he offered Turing a readership there. Turing resigned from the National Physical Laboratory to take up the post in Manchester. Newman writes in [13] that in Manchester:-

... work was beginning on the construction of a computing machine by F C Williams and T Kilburn. The expectation was that Turing would lead the mathematical side of the work, and for a few years he continued to work, first on the design of the subroutines out of which the larger programs for such a machine are built, and then, as this kind of work became standardised, on more general problems of numerical analysis.

In 1950 Turing published Computing machinery and intelligence in Mind. It is another remarkable work from his brilliantly inventive mind which seemed to foresee the questions which would arise as computers developed. He studied problems which today lie at the heart of artificial intelligence. It was in this 1950 paper that he proposed the Turing Test which is still today the test people apply in attempting to answer whether a computer can be intelligent [1]:-

... he became involved in discussions on the contrasts and similarities between machines and brains. Turing's view, expressed with great force and wit, was that it was for those who saw an unbridgeable gap between the two to say just where the difference lay.

Turing did not forget about questions of decidability which had been the starting point for his brilliant mathematical publications. One of the main problems in the theory of group presentations was the question: given any word in a finitely presented groups is there an algorithm to decide if the word is equal to the identity. Post had proved that for semigroups no such algorithm exist. Turing thought at first that he had proved the same result for groups but, just before giving a seminar on his proof, he discovered an error. He was able to rescue from his faulty proof the fact that there was a cancellative semigroup with insoluble word problem and he published this result in 1950. Boone used the ideas from this paper by Turing to prove the existence of a group with insoluble word problem in 1957.

Turing was elected a Fellow of the Royal Society of London in 1951, mainly for his work on Turing machines in 1936. By 1951 he was working on the application of mathematical theory to biological forms. In 1952 he published the first part of his theoretical study of morphogenesis, the development of pattern and form in living organisms.

Turing was arrested for violation of British homosexuality statutes in 1952 when he reported to the police details of a homosexual affair. He had gone to the police because he had been threatened with blackmail. He was tried as a homosexual on 31 March 1952, offering no defence other than that he saw nothing wrong in his actions. Found guilty he was given the alternatives of prison or oestrogen injections for a year. He accepted the latter and returned to a wide range of academic pursuits.

On 10 September 2009, the British Prime Minister Gordon Brown made an official public apology on behalf of the British government for the way in which Turing had been treated after the war.

Not only did he press forward with further study of morphogenesis, but he also worked on new ideas in quantum theory, on the representation of elementary particles by spinors, and on relativity theory. Although he was completely open about his sexuality, he had a further unhappiness which he was forbidden to talk about due to the Official Secrets Act.

The decoding operation at Bletchley Park became the basis for the new decoding and intelligence work at GCHQ. With the cold war this became an important operation and Turing continued to work for GCHQ, although his Manchester colleagues were totally unaware of this. After his conviction, his security clearance was withdrawn. Worse than that, security officers were now extremely worried that someone with complete knowledge of the work going on at GCHQ was now labelled a security risk. He had many foreign colleagues, as any academic would, but the police began to investigate his foreign visitors. A holiday which Turing took in Greece in 1953 caused consternation among the security officers.

Turing died of potassium cyanide poisoning while conducting electrolysis experiments. The cyanide was found on a half eaten apple beside him. An inquest concluded that it was self-administered but his mother always maintained that it was an accident.