Alan Turing

Alan Mathieson Turing was born in London in 1912 to the family of an official of the Indian civil service Julius Turing and Sarah Turing, born Stony. The Scottish surname Turing is of Norman origin. Anglo-Irish family Stony of Yorkshire origin gave the society several prominent physicists and engineers.

Alan Turing showed an interest in science, and in particular in mathematics, early, in elementary school and in the boarding house, which he entered in 1926. Some of the characteristics inherent in mature Turing were already noticeable then. Accepting this or that problem, he began to solve it from the beginning - a habit that gives freshness and independence to his works, but also, undoubtedly, makes the author difficult! readable.

In 1931, at the age of nineteen, Turing entered the Royal College of Cambridge as a mathematical fellow. Four years later, he defended his thesis “The Central Limit Theorem of Probability Theory” (which he himself “rediscovered” without knowing about similar previous work) and was elected a member of the Royal Scientific Society. It was in 1935 that he first began working in the field of mathematical logic and conducting research, which a year later led to outstanding results: the solution of one of D. Hilbert's problems and the invention of the speculative machine (Turing machine), which in its logical structure is a prototype of digital computers, created only ten years later.

The background to this was as follows. In Paris in 1900 at the International Congress of Mathematics, the famous mathematician David Gilbert presented a list of unsolved problems. In this list, the second was the problem of proving the consistency of the axiom system of ordinary arithmetic, the formulation of which Hilbert later clarified as the “Entscheidungs ​​problem” (the problem of solvability). It consisted in finding a general method that would allow one to determine “whether a given statement is feasible in the language of formal logic, that is, to establish its truth.”

Alan Turing first heard about this problem at the lectures of Max Newman in Cambridge (he worked there as a teacher of mathematics since 1924) and during 1936 he received the answer: the problem of Gilbert turned out to be insoluble. The results of the work he described in his famous article in the years 1936-1937. But “the significance of the article in which Turing stated his result,” wrote John Hopcroft, “extends beyond the scope of the task about which the article was written. Working on the Hilbert problem, Turing had to give a clear definition of the very concept of a method. Based on the intuitive idea of ​​the method as a kind of algorithm, that is, a procedure that can be performed mechanically (here, apparently, Turing used the terminology of M. Newman - a “purely mechanical process” used in a lecture setting forth the Hilbert problem) , without creative intervention, he showed how this idea can be embodied in the form of a detailed model of the computational process.

The resulting model of computation, in which each algorithm was divided into a sequence of simple, elementary steps, and was a logical construction, later called the Turing machine. ”

The significance of Turing's work for the theory of computation is great: “A Turing machine for a given large but finite period of time is able to cope with any computation that any powerful modern computer can perform.”

Turing was the first to reach an understanding of the universal nature of the computer. He showed that it is possible to build a universal machine that can work in the same way as any simple Turing machine, if you enter a description of this simple machine in it.

In September 1936, Turing left Cambridge and moved to America at Princeton University, where he works as a curator. There in 1938 he received his Ph.D. At that time, celebrities such as Church, Courant, Einstein, Hardy, von Neumann worked at Princeton University.

The first discussions on computational and “thinking” machines took place between Neumann and Turing. John von Neumann showed a keen interest in the idea of ​​a universal machine and offered Turing to work in Princeton as his assistant. Turing did not accept this offer and in the spring of the same year he returned to Cambridge, where he was confirmed the title and position of a member of the Royal College of the University.

The period of life and activities of Alan Turing from 1939 to 1945 for a long time was hidden by a veil of secrecy. Turing's mother, who published her memories of her son in 1959, wrote sparingly that, immediately after the declaration of war, Turing was hired as a civil servant in the communications department of the Ministry of Foreign Affairs. Initially, his whereabouts were kept secret, although it later became known that he worked in Bletchley Park near London, where special secret cryptanalysis work was carried out. Work in Bletchley Park was carried out in the framework of the secret project “Ultra”, whose goal was to find a method for decrypting secret German codes. To encrypt the secret orders of the Supreme Command of the Wehrmacht, the police apparatus, SD, SS in Germany, the electric Enigma encryption machine was used. Even before the start of World War II, the Poles were able to make an exact copy of the “Enigma” and ship it to England. But without a key and a switching circuit (the Germans changed them three times a day), even with another Enigma as a receiver, it was difficult to decrypt the message. In order to solve the secret cipher, a curious society of outstanding mathematicians, chess players, crossword puzzles, experts in various fields of knowledge, and even two musicians gathered in Bletchley Park. Alan Turing, who led one of the groups in which twelve mathematicians and four linguists worked, was among these people separated from the outside world. The work of his group and some others included the creation of various special computers for deciphering German messages. the brilliant ideas of the speculative “Turing machine” were embodied in real machines created in Bletchley Park. Among them were “Hit Robinson”, an electromechanical machine that included two photoelectric punched tape readers at a speed of 2000 characters per second (like an endless tape and a reading head of a “Turing machine”), an arithmetic unit for a relay and a printing unit, Peter Robinson “Super Robinson”, etc. Among the developers, besides Turing, were Winn-Williams, Flowers, and others. These machines worked on the principle of iterating over various combinations of characters from the German code before receiving a meaningful message. In September 1942, Professor M-Newman (the same from Cambridge) arrived in Bletchley Park and led a team of specialists (T. Flowers, A. Coombs, S. Broad-beat, U. Chandler, I. Good, D. Michie ) to create an electronic computer for the same purpose. As a result, in December 1943, the first (not only in England, but also in the world) electronic computer “Colossus” was created, containing 2000 electron tubes.

In this machine, only one type of tape was used, as suggested by A. Turing, “data” (in coded form, intercepted enemy messages per day), the reading speed from which reached 5000 characters per second (five photo readers were used). The machine, in the search for conformity, compared the encrypted message with the already known “Enigma” codes, which were stored in ring registers executed on tiratrons. By the end of the war about 10 “Colossi” had been made.

Obviously, Turing did not take direct part in the creation of the “Colossus”, he acted as a consultant, but as I. Good admitted, Newman’s work in 1936 helped him to create the car.

I do not want to say that we won the war thanks to Turing, - I. Good reminded many years later, - but I take the liberty to say that without him we could have lost it ”. For work in the Ministry of Foreign Years (in Bletchley Park) during the war A. Turing was awarded the Order of the Chevalier of the British Empire, IV degree.

The story of the encounter during the Tewing War with von Neumann still remains unclear. This story, or, as it was later called, the legend, is that this meeting of two prominent mathematicians was of decisive importance for the development of modern computer technology. It is known that Turing made at least one trip to the United States in 1943, although some claim that he had been there in 1942. Cro-me von Neumann, he also met with Claude Shannon, but they, obviously, did not discuss issues about computers. The relationship between these celebrities was probably best described by S. Frenkel, who wrote: “Many people proclaimed von Neumann the father of computers (in the modern sense of the term), but I am sure that he would never make such a mistake by himself. He (von Neumann) can be reliably called a “midwife”, and he insisted to me and others that the fundamental concept belongs to Turing, since neither Babbage, Lovelace, nor | others. "

In 1945, Alan Turing, refusing to lecture at Cambridge University, moved on the recommendation of M. Newman in the National Physical Laboratory (NFL), where the group was organized on the design and creation of computers ACE (Automatic Computing Engine). For three years (1945-1948), while this group existed, Om made the first sketches of ACE and made a number of proposals for its design. The Turing report on ACE is dated to a later date and refers to the well-known von Neumann draft report on EDVAC. But Turing went much further, since his work contained many specific details and had a complete computer concept with a stored program. Many argue that Turing was offered by one of the first projects of such a computer - a concept that is considered fundamental in the computing world and which was proposed to them independently of Mauchly, Eckert and Foch Neumann.

The ACE report was transmitted to the NFL Executive Committee on March 19, 1946 with a cover note by Womesley, which reported that although the report is based on the EDVAC project, the latter contains a number of ideas | owned by turing. Although the work of Turing during the war a lot! It is not known, it is certainly significant, at least for those points that are indicated in the ACE draft. A machine called MOSAIC, based on the primary version of this project, was soon built by Chandle-rum and Coombs.

In September 1948, Turing went to work at the University of Manchester, nominally assuming the position of deputy director of the computer laboratory, although in reality he was listed in the mathematical department of M. Newman and was responsible for programming.

At the University of Manchester since the end of 1940 under the guidance of f. Williams and T. Kilburna developed the computer “Mark-1 ″. On July 21, 1948, a 52-minute program was launched on the machine, and it is now believed that “Mark-1 ″ was the first operating computer with a stored program.

When working on the improvement of the Manchester machine, M. Newman was the first to come to the invention of the index register, and A. Turing wrote the first programming guide. In addition, Turing was invented another innovation. In the “Mark-1 ″ machine, a 5-bit code was used to represent the command, and each command contained 4 such codes, i.e., 20 bits. In order to facilitate programming, Turing proposed to assign a certain character from the set of 32 characters (25) to each 5-bit code according to the number of possible combinations. The characters that, according to Turing, corresponded to a five-digit binary code, contained numbers, letters and punctuation marks that are available on a standard teleprinter keyboard. For example, the symbol “/” (slash) was designated as 00000, the letter “R” - 01010, etc. In the future, as you know, computer symbols, including modern personal, began to occupy an 8-bit code (byte ). Their number can reach 256 different characters (28).

In the late 40s, Turing took up the problem of “thinking” machines, machine intelligence, which has now formed into a whole direction called “Artificial Intelligence”. Many scientists (in particular, J. Searle) consider Alan Turing to be the founder of artificial intelligence. His first article “Intelligent Machinery” in the form of a report of the National Physical Laboratory was published in 1948, and then in 1950 his main article “Computing Machinery and Intelligence” was published in the English journal “Mind”. In Russian translation, she came out under the name “Can a car think?”. And today, an analysis of this problem by Turing “has remained, perhaps, the best of all that is worth reading for everyone who wants to understand the essence of the matter.”

I'm going to consider the question “Can machines think?” - with these words, Turing begins an article, but soon he replaces the original question with a completely different one, in which the “thinking” of the machine is considered in technical terms. As a criterion for evaluating the thinker-Noah of the Turing machine activity, it suggests using its actions in the process of an “imitation game”. This “game” later received the name of the Turing test.

The modern understanding of the Turing test is interpreted as follows: if the machine is able to imitate behavior that the examiner cannot distinguish from the behavior of a person who has mental abilities telegraph), the machine also has these abilities. Since the 1950s, many papers have been published on how to programmatically implement the Turing test and what “can be hoped to be obtained from the modern level of heuristic programming”. A. Turing wrote about his hopes and forecasts at the end of the article: “We can hope that computers will eventually be able to compete with people in all purely intellectual fields of activity.

Полная функционирующая копия машины «Bombe» в Блэтчли-парке

But with what machines is the best place to start moving towards this goal? Even this question is difficult to answer. Many people think that the machine can best reveal their capabilities in an extremely abstract field, like a game of chess. It can also be argued that it would be best to supply the car with the best “senses” (sensors) from among those that can be bought, and then teach this machine to understand and speak English. This process may be similar to a child’s regular learning. That is, the car must point to a particular subject, name it, etc. I repeat that I do not know how to answer this question correctly, but I think that we should try to use these two approaches.

We can look ahead only for a very small distance, but it is already obvious that we still have a lot to do in the area that was the subject of this article. ”

Turing, as a person with non-traditional views, with the oddities of character, is remembered by many of his colleagues. There were legends about his eccentricities. Living in Cambridge, he never put the clock on the signals of the exact time, and calculated the time in the mind, noting the position of a particular star.

In Bletchley Park, at the beginning of June, strong attacks of hay fever (allergies) occurred to him every year, and then he came to work on a bicycle in a gas mask, fleeing pollen. His bike had a defect: the chain fell off at regular intervals. Instead of fixing it, he counted the number of revolutions of the pedals in order to get off the bike in time and straighten the chain. He tied, as I. Good recalls, with a chain of his mug to a heating radiator so that it would not be dragged off.

Once Turing, having learned about the fall of the British pound, melted the available silver coins and buried the ingot in the park, but then forgot where it was. Turing was a good athlete. After a howl, feeling the need for physical relaxation, he ran a long distance and found himself to succeed. Then he won the three-mile and ten-mile distances of his club, both times in record time, and in 1947 took the fifth place in the marathon race.

Many colleagues recall his enthusiasm and excitement, with which he took on any idea that interested him — from a “talking” hare to a difficult scientific problem. They looked at him with great respect, because he stood out for his intelligence and originality of thinking. He was described as an innate teacher, capable of solving and explaining any unusual problem. In addition, “not the last word is said about him as an engineer,” said W. Chandler.

Кроме выдающихся успехов, которых он добился в области компьютерной науки и машинного интеллекта, в области “чистой” математики Тьюринг получил ряд результатов в теории аппроксимации групп Ли, конечных групп и в вычислении дзета-функции Римана.

В конце жизни он занялся вопросами биологии, а именно разработкой химической теории морфогенеза, которая дала полный простор для его редкого сочетания способностей математика с точностью вычислительной машины и одаренного философа, полного смелых и оригинальных идей. Предварительный доклад 1952 года и отчет, который появился уже после его смерти, описывают только первые наброски этой теории.

Для восстановления здоровья Тьюринг обращался в большинстве случаев к домашним средствам. Он придумал игру под названием “Необитаемый остров”. Правила игры заключались в том, что все химические вещества (в том числе и лекарства) должны быть получены из бытовых продуктов. Так он получил цианистый калий и принял его. Утром 8 июня 1954 года его нашли в постели мертвым. Через несколько дней ему исполнилось бы 42 года.

Заслуги Алана Мэтисона Тьюринга в вычислительном мире велики. И, как свидетельство тому, известнейшая Ассоциация по вычислительной технике — ACM (Association for Computing Machnery, создана в 1947 году) учредила премию его имени. Первым лауреатом премии Тьюринга в 1966 году стал Алан Перлис (один из создателей АЛГОЛа) — первый президент АСМ. В дальнейшем этой премии удостаивались такие виднейшие ученые, как Джон Бэкус (создатель Фортрана), Джон Маккарти (создатель ЛИСПа, первый, кто ввел в практику термин “искусственный интеллект”), Кеннет Ай-версон (создатель АЛЛ), Герберт Саймон и Аллен Ньюэлл (создатели эвристического программирования) и др.

Many programming languages ​​are named after great mathematicians: EUCLID, PASCAL, BEBBIDG, etc. In 1982, scientists at the University of Toronto created a more powerful programming language than PASCAL and called it TURING.