Thought is material: Alan Turing as a “universal calculator”

Source: geektimes.ru

In the first half of the 20th century, when the first computers were invented. However, along with physically tangible machines, concept machines appeared. One of them was the "Turing machine" - an abstract computing device, invented in 1936 by Alan Turing - a scientist who is considered one of the founders of computer science.

His outlook extended from quantum theory and the principle of relativity to psychology and neuroscience. And as a way of knowing and transmitting their knowledge, Turing used the apparatus of mathematics and logic. He found solutions to seemingly unsolvable problems, but was most fascinated by the idea of ​​a “Universal Machine” capable of calculating everything that is in principle computable.
')

Childhood, education, hobbies

Alan's parents lived in the Indian city of Chhatrapur. Father - Julius Mathieson Turing, a representative of the old Scottish aristocratic family, worked in the Imperial public service. Mother - Sarah Ethel (nee Stoney), was originally from Ireland, from the Protestant family of the Anglo-Irish nobility. When she waited for the child, the couple decided to move to England so that he would grow up and be raised in London.

There Alan Turing and was born June 23, 1912. He had an older brother, John. The public service of Julius Turing continued, and Alan's parents often traveled between Hastings and India, leaving their two sons in the care of a retired army couple. Signs of genius manifested in Turing from early childhood.

In childhood, Alan and his elder brother John rarely saw their parents - their father served in India until 1926; the children remained in England and lived in care in private houses, receiving a strict English upbringing corresponding to their position on the social scale. Within the framework of such education, the study of the fundamentals of the natural sciences was not actually envisaged.



Little Alan had a very inquisitive mind. Learning to read independently at the age of 6, he asked permission from his educators to read non-fiction books.

At the age of 11, he set quite competent chemical experiments, trying to extract iodine from algae. All this was a source of great concern to his mother, who was afraid that his son’s hobbies, which run counter to traditional education, would prevent him from entering the Public School (an English private school for boys, which was obligatory for aristocratic children). But her fears were in vain: Alan was able to enroll in the prestigious Sherborne Public School.

At the age of six, Alan Turing went to St. Michael's School at Hastings, whose director immediately noted his talent. In 1926, at the age of 13, Turing went to the renowned private school of Sherborne in the city of Sherborne, Dorset. His first day at school coincided with the 1926 general strike. Therefore, Turing had to cover a distance of about 100 km from Southampton to Sherborne by bicycle, on the way he spent the night in a hotel.

Turing's fascination with mathematics did not find much support among teachers at the Sherborne School, where they paid more attention to the humanities. The school principal wrote to his parents: “I hope that he will not try to sit on two chairs at once. If he intends to stay in a private school, then he should strive to get an "education". If he is going to be an exclusively “scientific expert,” then a private school is a waste of time for him. ”



On Alan’s school successes is eloquently testified by a cool magazine in which you can find, for example, the following

I can see through his writings through my fingers, although I have never seen anything worse in my life, I try to endure his unshakable carelessness and indecent diligence; but I cannot, however, endure the amazing stupidity of his statements during the quite sound discussion of the New Testament.

However, in the areas of interest to him, Turing showed remarkable abilities.

In 1928, at the age of 16, Turing familiarized himself with the work of Einstein, in which he was able to sort it out to such an extent that he could guess from the text about Einstein’s doubts about the feasibility of Newton's Laws that were not expressed explicitly in the article.

University

Because of his dislike for the humanities, Turing did not get enough points on the exam, and so after school he entered King's College, Cambridge, although he intended to go to Trinity College. At King’s College, Turing studied from 1931 to 1934 under the guidance of the famous mathematician Godfrey Harold Hardy.

Cambridge University, which had special privileges granted by the English monarchs, has long been famous for its liberal traditions, and the spirit of free-thinking reigned in its walls. Here, Turing finds - perhaps for the first time - his real home, where he was able to fully surrender to science.

The main place in life was taken by a keen study of the sciences of so much interest to him - mathematics and quantum physics. Those years were a period of rapid development of quantum physics, and Turing, in his student years, became acquainted with the most recent works in this field. John von Neumann’s book The Mathematical Foundations of Quantum Mechanics, in which he finds answers to many of his long-standing questions, impresses him greatly.



Then Turing probably did not expect that in a few years von Neumann would offer him a place in Princeton - one of the most famous universities in the United States. Even later, von Neumann, as well as Turing, will be called the "father of computer science." But then, in the early 30s of the twentieth century, the scientific interests of both future eminent scientists were far from computers - both Turing and von Neumann are mainly engaged in the tasks of "pure" mathematics.

Turing came from an aristocratic family, but was never an “esthete”: Cambridge political and literary circles were alien to him. He preferred to do his favorite mathematics, and in his free time to put chemical experiments, solve chess puzzles.

Putting chemical experiments, he played a special game "Uninhabited island", invented by himself. The goal of the game was to obtain various "useful" chemicals from the "improvised means" - washing powder, dishwashing detergent, ink and the like "home chemistry".

He also found rest in intense sports activities - rowing and jogging. Marathon run will remain his true passion until the end of life.



Turing brilliantly completes a four-year course of study. One of his works, devoted to the theory of probability, is honored with a special award, he is elected to the scientific community of the Royal College. In 1935, Turing published the paper Equivalence of Left and Right Almost-Periodicity, in which he simplified von Neumann's one idea in the theory of continuous groups — the fundamental area of ​​modern mathematics. It seemed that he was waiting for a successful career of a slightly eccentric Cambridge teacher working in the field of "pure" mathematics.

However, Turing has never been held in any "framework". No one could have foreseen what kind of exotic problem would unexpectedly enthrall him, and what mathematically extraordinary way of solving it would be able to come up with.

In addition, in Cambridge, Alan attended the lectures of Wittenstein Ludwig. Wittenstein argued the theory of the failure of mathematics. According to him, mathematics does not seek truth, but creates it itself. Alan disagreed with this and argued a lot with Ludwig. Turing advocated "formalism" - a mathematical philosophical movement that did not require an exact translation of words and was limited to exemplary meaning. And Ludwig was looking for absolute precision.

While studying at college, Alan Turing studied the basics of cryptography — that is, decrypting data. This was useful to him during the Second World War, when a scientist worked on deciphering German messages.

Turing Machine

In 1928, the German mathematician David Hilbert drew the attention of the world community to the problem of resolution (Entscheidungsproblem). In his work On Computable Numbers, with an Application to the Entscheidungsproblem, published November 12, 1936. Turing reformulated Gödel’s incompleteness theorem, replacing Gödel’s universal formal arithmetic language with simple hypothetical devices that later became known as Turing machines.

He proved that such a machine would be able to perform any mathematical calculations that can be represented as an algorithm. Further, Turing showed that there is no Entscheidungsproblem solution, first proving that the Stop Problem for a Turing Machine is unsolvable: in general, it is impossible to determine algorithmically whether a given Turing machine will ever stop.

Although Turing's evidence was made public soon after the equivalent proof of Alonzo Church, in which the Lambda calculus were used, Turing himself was not familiar with it. The approach of Alan Turing is considered to be more accessible and intuitive. The idea of ​​a "Universal Machine" capable of performing the functions of any other machine, or in other words, to calculate everything that can, in principle, be calculated, was extremely original. Von Neumann acknowledged that the concept of a modern computer is based on the work of Alan Turing. Turing machines are still the main object of study of the theory of algorithms.



To the question : “What is a Turing machine and how does it relate to programming?” One of the Toster users answered:

First of all - this is a formal definition of the algorithm. A task is considered algorithmically solvable if and only if its solution can be programmed on a Turing machine (or in some other equivalent way). This definition gives, for example, the ability to present algorithmic unsolvable problems. Allows you to enter the concept of "Turing-complete" language - if you can implement a Turing machine in a language, then you can write any algorithm on it (C preprocessor is not, and C # is).

In general, MT is a way to define some class of algorithms:

- some tasks can be solved by the state machine;
- for some, a state machine with a stack memory is required;
- for others, enough Turing machines;
- For the rest, divine revelation or other non-algorithmic methods are required.

From September 1936 to July 1938 Turing worked under Church’s leadership at Princeton. Besides studying mathematics, the scientist studied cryptography and also designed an electromechanical binary multiplier.



In June 1938, Turing defended his doctoral thesis “Logic systems based on ordinals,” which presented the idea of ​​Turing information, which was to combine the Turing machine with an oracle. This allows you to investigate problems that cannot be solved with a Turing machine alone.

Cryptanalysis

During World War II, Alan Turing took an active part in hacking German ciphers at Bletchley Park. The historian and veteran of Bletchley Park, Eisa Briggs, once said:

"Bletchley Park needed exceptional talent, exceptional genius, and Turing's genius was just that."

Since September 1938, Turing worked part-time at GCHQ, a British organization specializing in cipher cracking. Together with Dilly Knox, he was engaged in cryptoanalysis of "Enigma". Shortly after the meeting in Warsaw in July 1939, at which the Polish Cipher Bureau provided Great Britain and France with detailed information about the connections in the Enigma rotors and the message decryption method, Turing and Knox began their work on a more solid way to solve the problem.

The Polish method was based on flaws in the indicator procedure, which the Germans corrected by May 1940. Turing's approach was more general and based on the method of iterating through source code sequences for which he developed the initial functional specification Bombe.

The machine, created on the basis of this specification, looked for possible settings used to encrypt messages (rotor order, rotor position, patch panel connection), based on known plaintext. For each possible setting of the rotor (which had 10 ^ 19 states or 10 ^ 22 in the modification used on submarines), the machine produced a number of logical assumptions based on the plaintext (its content and structure).

Next, the machine determined the contradiction, discarded a set of parameters and proceeded to the next. Thus, most of the possible sets were eliminated and only a few options remained for careful analysis.
The first car was put into operation on March 18, 1940. The search for keys was done by rotating mechanical drums, accompanied by a sound similar to the ticking of a clock.



The specification for "Bombs" was only the first of Turing's most important five achievements in the field of military cryptanalysis.

The scientist also determined the indicator procedure of the German Navy; developed a more efficient way to use Bombe, based on statistical analysis and called "Banburismus"; the method of determining the parameters of the wheels of the Lorenz machine, called the "Turierium"; near the end of the war, Turing developed the Delilah portable speech encoder.

The statistical approach to optimizing research on various probabilities in the process of deciphering ciphers that Turing used was a new word in science. Turing wrote two papers: “Report on the applicability of a probabilistic approach in cryptoanalysis” and “A document on statistics and repetitions”, which were of such value for GCCS, and later for GCHQ (Government Communications Headquarters) that they were not provided to the national archive until April 2012, shortly before the celebration of one hundred years since the birth of the scientist. One of the employees of GCHQ said that this fact speaks of the unprecedented importance of this work.

Turing was also engaged in the development of ciphers for Churchill and Roosevelt correspondence, spending the period from November 1942 to March 1943 in the United States.

In 1945, Turing was awarded the Order of the British Empire by King George VI for his military service, but this fact remained secret for many years.

Post-war years

After von Neumann in the United States proposed a plan for creating an EDVAC computer, similar work was launched in the UK at the National Physical Laboratory, where Turing had worked since 1945. The scientist proposed a very ambitious project ACE (Automatic Computing Engine - Automatic Computing Machine), which, however, was never implemented.

Despite the fact that the construction of ACE was quite feasible, the secrecy surrounding Blatchley Park led to delays in the start of work, which disappointed Turing.

1947–1948 academic year Turing spent in Cambridge. While Alan Turing was in Cambridge, the Pilot ACE was built in his absence.


Franklin ACE 1200

He completed his first program on May 10, 1950. Although the full version of ACE was never built, some computers had a lot in common with it, for example, DEUCE and Bendix G-15.

In May 1948, he received an offer to take the post of teacher and deputy director of the computing laboratory at the University of Manchester, who by this time occupied the leading position in the development of computing technology in the UK.

In 1948, Alan, together with his former colleague, began writing a chess program for a computer that did not exist yet.

In the same year, Turing invented the LU decomposition method, which is used to solve systems of linear equations, inverse matrices, and calculate the determinant.

Turing Test

In 1948, Alan Turing received the title of Reader in the mathematical department of the University of Manchester. There, in 1949, he became director of a computer lab, where the programming work of Mark I. Manchester was concentrated.

At the same time, Turing continued to work on more abstract mathematical problems, and in his work Computing Machinery and Intelligence (Mind magazine, October 1950) he addressed the problem of artificial intelligence and proposed an experiment that later became known as the Turing test.

His idea was that it can be considered that a computer “thinks” if a person interacting with it cannot distinguish a computer from another person in the process of communication. In this work, Turing suggested that instead of trying to create a program that simulates the mind of an adult, it would be much easier to start with the mind of the child, and then teach it. CAPTCHA, based on the reverse Turing test, is widely distributed on the Internet.

In 1951, Turing was elected a member of the Royal Society of London.



In the original formulation, the “Turing test” implies a situation in which two people, a man and a woman, communicate through a certain channel excluding voice perception, with a third person separated from them, who tries to determine the gender of each of his interlocutors by indirect questions; while the man tries to confuse the questioner, and the woman helps the questioner to find out the truth.

The question here is whether the machine will be equally successful in this “imitation game” instead of the man (will the questioner err in his conclusions so often)? Subsequently, the simplified form of the test became widespread, in which it becomes clear whether a person, communicating in a similar situation with a certain interlocutor, can determine whether he communicates with another person or with an artificial device.

This mental experiment had a number of fundamental consequences. First, he proposed some operational criteria for answering the question "Can a car think?".

Secondly, this criterion turned out to be linguistic: this question was explicitly replaced by the question of whether the machine can adequately communicate with a person in a natural language. Turing wrote directly about the replacement of the wording and at the same time expressed confidence that "the method of questions and answers is suitable to cover almost any area of ​​human activity that we want to introduce into consideration."

The consequence of this was the crucial role that, in the further development of artificial intelligence, in any case, until the 1980s, research on the modeling of the understanding and production of natural language played. In 1977, the then director of the laboratory of artificial intelligence at the Massachusetts Institute of Technology, P. Winston, wrote that teaching a computer to understand natural language is the same as building an intelligence in general.


Source: slideshare.net

Memory

• one of the asteroids is named after the scientist;

• the annual award of the Computer Engineering Association is called the Turing Award;

• on the main square of the University of Surrey (England) there is a statue of Turing and one of the buildings of the Faculty of Engineering and Physical Sciences is named after him;

• one of the audiences of the computer science department at the University of Lille in Northern France is named after Alan M. Turing;

• University of Manchester, Open University, University of Oxford Brooks and Aarhus University (Denmark) have Turing buildings and others;

• in 2001, a monument to the scientist was erected in Manchester.