Year of Alan Turing in the world and Ukraine The essence of the event Organizers Statistics Life path Tragedy of personal life Recognition Modern explications of Turing's theory Variants of interpretation of the test Criticism of the test Predictions Achievements and contributions to science Cryptography Turing machine Turing test
More than 70 universities around the world More than 50 organizations - partners of the project More than 80 planned events International scientific and creative competitions, competitions for scholarships Exhibitions dedicated to Alan Turing and his activities Cycles of film and television screenings Publication of a number of books A number of events that will be held during 2012 years in many countries around the world. A significant portion of the events will be held in places that had special significance in the life of Alan Turing - Cambridge, Manchester and Bletchley Park. (The Turing Centenary, The Alan Turing Year)
(Alan Mathison Turing) June 23, 1954 Great Britain Introduced the mathematical concept of an abstract equivalent of an algorithm, or computable function, which was then called a “Turing machine.” He was one of the first to raise the question of the ability of a computer to think, that is, the question of artificial intelligence, and was the first to propose a criterion for assessing the thinking abilities of a machine. Contributed to cryptography, mathematics, logic and all further developments in computer science. He is often called the “father of computer science,” the founder of the theory of artificial intelligence, the first theorist of modern programming, and even the world’s first hacker.
The roots of the Turing family go back to the 14th century, to the old Scottish family of baronets Turins of Foveran from Aberdeenshire. Grandfather, John Robert Turing: degree in mathematics from Cambridge. Father, Julius Matheson Turing: BA History and Literature, Oxford; study of Indian history and languages. Mother, Ethel Sarah Stoney: studied art and music at the Sorbonne. The Stoney family: a well-known family in the scientific world that gave the world the famous physicist George Stoney, a member of the English Royal Society. “A person’s biography never begins from the moment of his birth. Moreover, the biography of a true genius. Indeed, in order for a physical and spiritual structure to arise in which genius would manifest itself in all its fullness, an unusually systematic interaction is necessary, a mixing of genes and chromosomes, inexplicable forces and matters, and over the course of several generations.”
Dismal performance... Hopelessly behind... He is one of those students who creates problems for any school and the whole society Reviews of school teachers Alan Turing If he remains in school, he must set himself the goal of becoming educated. If he is only supposed to be a scientist, then he is wasting his time here.” Books That Shocked: Natural Wonders Every Child Should Know About (Edwin Brewster) The Nature of the Physical World (Arthur Eddington) Alan Turing Alan Turing aged 16
The turning point in Turing's life was his acquaintance with Christopher Morcom, with whom he was united, among other things, by an interest in mathematics and astronomy. Christopher Morcom They dreamed of changing the world together. We prepared and took exams at Cambridge together. Christopher was accepted, but Alan was not. In February 1930, Chris suddenly became ill. He was taken to the hospital and had two operations, but it didn’t help, and a week later he died. The cause was tuberculosis, which he contracted in childhood. Alan Turing decided that now he had to live not only for himself, but also for him, and had to accomplish in science what Chris could not. Chris's work was always better than mine, Turing wrote, "he was incredibly gifted."
King's College, Cambridge Books that shocked: Mathematical foundations of quantum mechanics, (John von Neumann) Werner Heisenberg, Erwin Schrödinger (works on quantum mechanics) Introduction to mathematical philosophy (Bertrand Russell) Foundations of arithmetic (Gottlieb Frege) Master's thesis: Central limit theorem theory of probability Scientific supervisor (and colleague in the rest of his life): mathematician (topologist) Max Newman (). Maxwell Herman Alexander "Max" Newman
Church–Turing thesis: proof of the fundamental undecidability of the “decidability problem” (proof of the consistency of the axiom system of ordinary arithmetic) by David Hilbert. A refutation of the hopes of D. Hilbert and his followers, who believed that mathematics, as the most formalized part of human knowledge, can be represented as a set of axioms and theorems. It was to solve this problem that Turing developed the concept of an abstract digital computer. A clear definition of the concept of a method as a certain algorithm that can be performed mechanically, without creative intervention. Model of the computing process: each algorithm is divided into a sequence of simple, elementary steps. Inefficiency of building specialized computers and the idea of a universal electronic computer. This logical construction was subsequently called the “Turing machine”. (History of creation)
(working principle) An extremely simple and extremely general schematic diagram of an automatic computer. Conclusions: Any computational or logical process for which an algorithm exists can be automated using such a primitive machine. And vice versa: everything that can be done with this machine is subject to an algorithm. Problems that cannot be solved by this machine are algorithmically unsolvable for any, even the most powerful, machine, not only of today, but also of the future. Only the human brain can cope with algorithmically unsolvable problems.
(physical embodiment of the idea of a computer) Princeton University, obtaining a PhD degree. Work with Alonzo Church, John von Neumann, Albert Einshein and other outstanding physicists and mathematicians. First discussions on computing and thinking machines with John von Neumann. Cambridge again: work at the Cambridge National Physical Laboratory in the group on the design and creation of the ACE (Automatic Computing Engine) computer. Manchester: Worked in Max Newman's mathematics department to develop a computer as a programming supervisor. July 21, 1948: launch of the first program on the created Mark-1 computer: the first working computer with a stored program. Writing the first programming manual and the first chess program.
(decoding Enigma codes) Enigma cipher machine Work at the National Codes Center in Bletchley Park as part of the secret Project Ultra, the purpose of which was to find a method for deciphering secret German codes created using the Enigma electrical cipher machine. Creation of special computers for deciphering German messages (“Heath Robinson”, “Peter Robinson”, “Bomb” and others). Participation in the creation of the Colossus - the first (not only in England, but also in the world) fully electronic computer (under the leadership of M. Newman). “I don’t want to say that we won the war thanks to Turing, but I take the liberty of saying that without him we might have lost it. I. Good
(posing the question of artificial intelligence) Mid-20th century: the emergence of interest in artificial intelligence as a new scientific direction. The articles Intelligent Machinery (1948) and Computing Machinery and Intelligence, subsequently republished as "Can the Machine Think?" (Can a Machine Think?) (1950). The question is not “can a machine think?”, but “can a machine do what we (as thinking creatures) can do, that is, what we call “thinking.” “The Imitation Game” as a criterion for assessing the mental activity of a machine. Consequences: For the first time, some operational criterion has been proposed to answer the question “Can a machine think?” Linguistic Approach: The question of whether a machine can think is reduced to the question of whether a machine can adequately communicate with a human in natural language. (according to Turing, “the method of questions and answers is suitable for covering almost any field of human activity that we wish to introduce into consideration”).
Persecution for homosexuality, charges of “indecent behavior.” March 31, 1953 - trial and verdict: imprisonment, or injections of the female hormone estrogen (a method of chemical castration). He chose the latter. Dismissal from the Codes Department. 8 June 1954: Alan Turing's body is discovered by a housekeeper. The verdict of the investigation: suicide by potassium cyanide poisoning. 10 September 2009: British Prime Minister Gordon Brown publicly apologized for the persecution suffered by Alan Turing and thousands of other gay men convicted under homophobic laws. Apple... a biblical symbol of knowledge and sin, a symbol of tragic love and death of Turing himself; an allusion to the apple that inspired Isaac Newton's theory of gravity; the famous Apple logo with a bitten apple...
A new wave of popularity for Alan Turing begins at the very end of the 20th century, when he becomes known not only and not so much for his contributions to computer science and mathematics, but as a person who suffered because of his unconventionality, a kind of cultural hero, a symbol and hope of all persecuted and persecuted. A huge amount of biographical and research literature. Mentions in historical and fantasy novels by Neal Stephenson, Robert Harris, Harry Harrison, Marvin Minsky, William Gibson. At least two operas and several songs, including in Chinese. London's West End and Broadway production of the award-winning play "Breaking the Code": the film "Breaking the Code"; 2011: film "The Imitator's Game" (not completed). 2002: Ranked 21st in the BBC's 100 Greatest Britons of History list. 1999: Time magazine named Turing one of the 100 most important people of the 20th century.
In 1974, the Association for Computing Machnery (ACM) established the Alan Turing Award, recognized in the global computer community as the highest award. Also named after Alan Turing: Monuments and monuments: in Bletchley Park, on the territory of the University of Oregon, on the territory of the University of Surrey, in Sackville Park in Manchester. Computer laboratories of a number of universities. Alan Turing Road on the campus of the University of Surrey (UK); The ring road around Manchester is called The Turing Way, and the bridge it runs over is called the Alan Turing Bridge. (The Alan Turing Bridge). Academic buildings at the universities of Manchester, Oxford Brookes, University of Manchester, the Open University, Oxford Brookes University and Aarhus University (Dani), International School of Information Sciences (France), etc. Annual conferences and competitions in a number of cities around the world. A programming language created in 1982 by scientists at the University of Toronto. Monument to Alan Turing on the campus of the University of Surrey (UK)
Today, more than 50 years after Turing published the first results of his work in the field of artificial intelligence, the questions he posed remain relevant and, moreover, give rise to new interpretations. Among them: Minimum Intelligent Signal Test (MIST). Suggested by Chris McKinstry. Only two types of answers are allowed: “yes” and “no”. Used to collect statistical information to measure the performance of programs that implement artificial intelligence. Immortality test. Determines whether a person’s character is conveyed qualitatively, namely, whether it is possible to distinguish the copied character from the character of the person who served as its source. Meta Turing test. An entity (in particular, a computer) is considered intelligent if it has created something that it itself wants to test for intelligence. Reverse Turing test. A modification of the Turing test in which the goal or one or more of the machine and human roles are reversed. The computer's task is to determine who it was talking to: a person or another computer. CAPTCHA (from English: Completely Automated Public Turing test to tell Computers and Humans Apart). A type of reverse test. The goal is to prevent attacks by automated systems on the site.
Excessive anthropomorphism: only the ability of the machine to resemble a person is tested, and not the intelligence of the machine in general. The test does not take into account the following possibilities: Sometimes a person's behavior defies reasonable interpretation. Some intelligent behavior is not inherent in humans. The Turing Test has been criticized on several grounds: Impracticality: The anthropomorphism of the test means that it cannot be truly useful in the development of intelligent machines. For example, in aircraft design we are not at all striving to create an intelligent machine that makes human errors. Possibility of simulating intelligence: The Turing test is clearly behaviorist or functionalist: it only tests how the subject acts. A machine passing the test can imitate human conversational behavior simply by “non-intelligently” following mechanical rules (a famous example: American philosopher John Rogers Searle’s “Chinese Room” thought experiment).
In the article “Is the Brains Mind a Computer Program?” ("Is Brain Thinking a Computer Program?"), published in 1990, Searle describes proving that when the Turing test is administered, there is no way to distinguish a program's truly mental activity from the mechanical execution of properly prepared instructions. (“Chinese Room” by J.R. Searle)
Turing predicted that machines would eventually be able to pass the test he developed. He even named specific dates: by the year 2000, machines with a memory capacity of about 125 MB) will be able to deceive 30% of judges. To date, not a single program has been able to pass the test. The Loebner Prize is a $100,000 prize established in 1990 by American scientist and philanthropist Hugh Loebner and awarded to the winner of an annual competition in which computer programs compete to pass the Turing test. Eliza (ELIZA) (named after Eliza Doolittle from the play Pygmalion by Bernard Shaw) is one of the first programs to take part in the Loebner Competition; created by German-American scientist Joseph Weizenbaum in 1966. A.L.I.C.E. (an abbreviation for Artificial Linguistic Internet Computer Entity, which can literally be translated as “Artificial Linguistic Internet Computer Entity”) is a leader in its kind of program, which won the Loebner Prize three times (in 2000, 2001, 2004). Interlocutor program A.L.I.C.E.
So, obviously, it must be recognized that Alan Turing's predictions regarding artificial intelligence have not come true to date, and therefore the question “can a machine think?” still remains open. As well as the questions: should a machine think? Should a machine think exactly the way a person does? Is the question of a virtual mind achieving indistinguishability from a human one really that important? And many others…
100 years since the birth of Alan Turing Yulia Kiseleva Master's student in religious studies, Donetsk National Technical University Presentation materials are available on the website of the Association of Philosophers and Religious Studies:
Definition of a Turing machine
A Turing machine is an abstract executor that carries out an algorithmic process, created to clarify the concept of an algorithm. It is a mathematical object, not a physical machine. Proposed by Alan Turing in 1936, a Turing machine is a rigorous mathematical construction, a mathematical apparatus created to solve certain problems.
Structure and description of the Turing machine The Turing machine consists of: an infinite tape divided into cells; carriages (reading and writing heads); programmable machine (program in table form). The machine “sees” only one cell each time. Depending on what letter it sees, and also depending on its state q, the automaton can perform the following actions: write a new letter in the observed cell; move the tape one cell to the right/left or remain motionless; move to a new state.
1) External alphabet A = ( a 0 , a 1 , …, a n ) The element a 0 is called an empty symbol or an empty letter (a sign that the cell is empty). In this alphabet, the original data set and the result of the algorithm are encoded in the form of a word. Turing machine design
2) Internal alphabet Q = ( q 0 , q 1 , …, q m ), ( P, L, N! ) At any moment of time the Turing machine is in one of the states q 0 , q 1 , …, q m In this case: q 1 - initial state (the machine starts working) q 0 - final state (the machine has finished working) Symbols (P, L, N!) - shift symbols (right, left, in place) Turing machine structure
Types of Turing machine commands Write a new letter in the observed cell Shift along the tape one cell to the right/left or remain in place (R, L, N) Go to a new state. a 0 a 1 … a i … a j q 0 q 1 … a k ( LPN ) q m q i … q j 1 1 1 * 1 1 Indication of character change Indication of carriage shift Indication of internal state change
3) External memory (tape) The machine has a tape divided into cells, in each of which only one letter can be written. Structure of a Turing machine
3) External memory (tape) Turing machine design An empty cell contains a 0 . At each moment of time, a finite number of non-blank letters are written on the tape. The tape is finite, but is supplemented at any moment with cells on the left and right to record new non-blank characters. This corresponds to the principle of abstraction of potential feasibility
4) Carriage (control head) The carriage of the machine is located above a certain cell of the tape - it perceives the symbol written in the cell. In one cycle of work, the carriage moves one cell (right, left) or remains in place The design of the Turing machine
5) Functional diagram (program) The machine program consists of commands: Turing machine structure For each pair (q i, a j) the machine program must contain one command (deterministic Turing machine)
When the machine starts operating, the initial set of data in the form of a word is supplied to the tape. Description of the operation of the Turing machine We will say that a non-empty word in the alphabet A\ (a 0 ) is perceived by the machine in a standard position if: - it is specified in successive cells of the tape, - all other cells are empty - the machine looks at the rightmost cell of those in which the word is written
Description of the operation of a Turing machine A standard position is called initial (final) if the machine that perceives a word in the standard position is in the initial state q 1 (stop state q 0)
Being in a non-final state, the machine takes a step, which is determined by the current state q i and the observed symbol a j Description of the operation of a Turing machine
Description of the operation of a Turing machine In accordance with the command q i a j q k a l X, the following actions are performed: 1) The contents of the observed cell a j are erased and the symbol a l (which may coincide with a j) is written to it 2) The machine goes to a new state q k (it may coincide with the state q i) 3) The carriage moves according to the controlled symbol X (R, L, N!)
When the machine transitions to the final state q 0, its work stops. The result of the algorithm is written on the tape - the word in the alphabet A\ (a 0) Description of the operation of the Turing machine
A machine word (configuration) of a Turing machine is a word of the form 1 q k a l 2 , where 1 and 2 are words in the alphabet A.
The configuration 1 q k a l 2 is interpreted as follows: - the machine is in state q k - the carriage scans the symbol a l on the tape - 1 and 2 are the contents of the tape before and after the symbol a l
Situations of inapplicability of a Turing machine It is considered that a Turing machine is inapplicable to a given input word if there are no stopping cells in the program or the machine does not hit them during operation. For example: A Turing machine is applicable to a given input word if, having started working on this input word, it sooner or later reaches one of the stop cells. How has the example program changed? а 0 0 1 q 1 1П q 1 0П q 1 1П q 1 а 0 0 1 q 1 1Н q 0 0П q 1 1П q 1
Example of Turing machines It is required to build a Turing machine to solve the following problem: in the input word, replace all the letters “a” with the letters “b” and vice versa. a 0 a b c ... i q 1 a 0 N! b L q 1 a L q 1 in L q 1 … i L q 1 y y b a a b r r u b a r a b a b b a a b b a
Implement the proposed algorithm: The Turing machine adds one to the number on the tape. The input word consists of the digits of a decimal integer number written into successive cells on the tape. At the initial moment, the machine is located opposite the rightmost digit of the number. а 0 0 1 2 3 4 … 7 8 9 q 1 1Н q 0 1Н q 0 2Н q 0 3Н q 0 4Н q 0 5Н q 0 … 8Н q 0 9Н q 0 0Л q 1
Implement the proposed algorithm. The Turing machine tape contains a sequence of symbols “+”. The Turing machine replaces every second “+” symbol with a “–”. The replacement starts from the right end of the sequence. The automaton in state q 1 examines one of the symbols of the specified sequence. a 0 + – q 1 a 0 L q 2 + P q 1 q 2 a 0 N! + L q 3 q 3 a 0 N! – L q 2 q 1 – the machine searches for the right end of the number; q 2 – skips the “+” sign, when reaching the end of the sequence – stop; q 3 – the “+” sign is replaced by “–”.
Example Given a Turing machine with an external alphabet A = ( a 0 , 1, * ), an alphabet of internal states Q = ( q 0 , q 1 , q 2 , q 3 ), and the following functional diagram: Apply the Turing machine to the word =11 *1, starting from standard starting position
Solution 1) Replace the contents of the observed cell 1 with 0
Solution 2) The machine goes into a new state q 2
Solution 3) The carriage moves to the left
Solution Full Detailed Solution
Solution Full Detailed Solution
Solution Solution written using configurations (in a line)
= 1*11 Answer: = 111
Literature Igoshin V.I. Mathematical logic and theory of algorithms. – M.: Academy, 2008. - 448 p. Likhtarnikov L.M., Sukacheva T.G. Mathematical logic. Lecture course. Workshop problem book and solutions. – St. Petersburg: Lan, 1999. - 288 p. Ilinykh A.P. Theory of algorithms. Tutorial. – Ekaterinburg, 2006. - 149 p.
People can behave differently in the same situations, and this is what makes them fundamentally different from machines.
Alan Turing (1912 – 1954)
Alan Turing's future parents, Julius Matheson Turing and Ethel Sarah Stoney, met and got married in India. Turing served in the English Colonial Office, and Ethel Sarah was the daughter of the chief engineer of the Madras Railways. This was a respectable English aristocratic family, belonging to the so-called “upper middle class” and living in accordance with the strict traditions of the Empire.
Alan Matheson Turing was born in London in 1912 year. The Scottish surname Turing is of Norman origin. The Anglo-Irish Stoney family of Yorkshire origin gave the society several outstanding physicists and engineers.
A year after giving birth, Turing's mother returned to India, leaving Alan in the care of a family friend, a retired colonel. Later the boy was sent to a private boarding school.
Little Alan had a very inquisitive mind. Having independently learned to read at the age of six, he asked his teachers for permission to read popular science books. At the age of 11, he performed quite competent chemical experiments, trying to extract iodine from algae. All this caused great concern to his mother, who was afraid that her son’s hobbies, which ran counter to traditional upbringing, would prevent him from enrolling in Public School (an English closed private educational institution for boys, studying in which was compulsory for children of aristocrats). But her fears were in vain: Alan was able to enter the prestigious Sherborne Public School. However, she soon had to fear whether her talented son would be able to graduate from this school...
Alan Turing showed an interest in science, and in particular mathematics, early, in primary school and at the boarding school he attended at 1926 year. Some characteristic features inherent in the mature Turing were noticeable even then. When taking on a particular task, he began solving it from the beginning - a habit that gives freshness and independence to his work, but also, undoubtedly, makes it difficult for the author! readable.
A youthful thirst for knowledge quickly brought Turing and Morcom closer together, and they became inseparable friends. Now they were already yawning together in French lessons or playing tic-tac-toe, while simultaneously discussing astronomy and mathematics. After leaving school, they were both planning to enter Cambridge University, and Alan, having gotten rid of many years of loneliness, may have been almost happy...
February 13 1930 Mr. Chris suddenly passed away. The sudden death of his best friend shocked seventeen-year-old Turing, plunging him into a deep and long depression.
IN 1931 At the age of nineteen, Turing entered King's College, Cambridge University, as a mathematics fellow. Four years later he defended his thesis “The Central Limit Theorem of Probability Theory” (which he independently “rediscovered”, not knowing about similar previous work) and was elected a member of the Royal Scientific Society.
IN 1932 year, during one of his visits to the Morcom family, he draws up a document in their house called “The Nature of the Spirit” - a manifesto of his belief in the existence of the human Spirit after death. The main point of this work is that the determinism of the traditional physical picture of the world and its obvious contradiction with the idea of free will are refuted by the new science - quantum physics.
The question of the structure of the human mind will worry him all his life.
In September 1936 Turing leaves Cambridge and moves to America to Princeton University, where he works as a curator. there in 1938 year he receives his Ph.D. At that time, such celebrities as Church, Courant, Einstein, Hardy, and von Neumann worked at Princeton University.
Exactly at 1935 year, 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 a speculative machine (Turing machine), which in its logical structure is a prototype of digital computers created only later ten years.
The background to this was as follows. In Paris in 1900 At the International Congress of Mathematics, the famous mathematician David Hilbert presented a list of unsolved problems. The second on this list was the task of proving the consistency of the system of axioms of ordinary arithmetic, the formulation of which was later clarified by Hilbert as the “Entscheidungs problem” (the problem of solvability). It consisted in finding a general method that would make it possible 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 Max Newman's lectures at Cambridge (he worked there as a mathematics teacher with 1924 year) and during 1936 year received the answer: Hilbert's problem turned out to be unsolvable. He described the results of his work in his famous article in 1936 - 1937 years. But “the significance of the paper in which Turing presented his result,” wrote John Hopcroft, “extends beyond the scope of the problem for which the paper was written.
While working on Hilbert's problem, Turing had to give a clear definition of the very concept of a method. Starting from the intuitive idea of a method as a kind of algorithm, i.e., a procedure that can be performed mechanically (here, apparently, Turing used the terminology of M. Newman - “a purely mechanical process”, used in a lecture presenting Hilbert’s problem) , without creative intervention, he showed how this idea could be translated into a detailed model of a computational process.
The resulting model of calculations, in which each algorithm was divided into a sequence of simple, elementary steps, was a logical construction, later called a Turing machine.”
The significance of Turing's work for the theory of computation is great. : “The Turing machine, for a given large but finite period of time, is capable of coping with any calculation that can be performed by any modern computer, no matter how powerful.”
The period of life and work of Alan Turing from 1939 By 1945 The year was hidden for a long time under a veil of secrecy. Turing's mother, who published in 1959 year memories of her son, she sparingly wrote that immediately after the declaration of war, Turing was hired as a civil servant in the communications department of the Foreign Office. At first his whereabouts were kept secret, although it later became known that he worked at Bletchley Park near London, where highly secret cryptanalysis work was carried out. The work at Bletchley Park was carried out as part of the secret Project Ultra, the purpose of which was to find a method for deciphering secret German codes.
In 1939, the British War Department tasked Turing with unraveling the secret of Enigma, a special device used to encrypt radio messages in the German Navy and Luftwaffe. British intelligence obtained this device, but it was not possible to decipher the intercepted German radiograms.
To encrypt the most secret orders of the Supreme Command of the Wehrmacht, the police apparatus, the SD, and the SS in Germany, the Enigma electric encryption machine was used. Even before the start of World War II, the Poles managed to make an exact copy of Enigma and transport 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 decipher the message. To solve the secret code, a curious society of outstanding mathematicians, chess players, crossword puzzle enthusiasts, experts in various fields of knowledge and even two musicians gathered at Bletchley Park. Among these people, cut off from the outside world, was Alan Turing, who led one of the groups in which twelve mathematicians and four linguists worked.
27-year-old Turing and his colleagues were seized with real sports passion. The Germans considered Enigma impregnable. The difficulty of deciphering was aggravated by the fact that the encoded word contained more letters than the original. However, within six months Turing developed a device, which he called the “Bomb,” which made it possible to read almost all messages from the Luftwaffe. And a year later, a more complex version of Enigma, used by Nazi submariners, was “hacked.” This largely predetermined the success of the British fleet.
At the University of Manchester from the end 1940 years under the leadership of f. Williams and T. Kilburn developed the Mark-1 computer. 21 July 1948 A 52-minute program was run on the machine in 1999, and it is now believed that the Mark 1 was the first working stored program computer.
While working on improving the Manchester machine, M. Newman was the first to come up with the invention of the index register, and A. Turing wrote the first programming manual. In addition, Turing came up with another innovation. The Mark-1 machine used a 5-bit code to represent a command, with each command containing 4 such codes, i.e. 20 bits.
In order to facilitate programming, Turing proposed assigning each 5-bit code a specific symbol from a set of 32 characters (25) - according to the number of possible combinations. The symbols that Turing believed corresponded to a five-digit binary code contained the numbers, letters, and punctuation marks found on a standard teleprinter keyboard. For example, the character “/” (slash) was designated 00000, the letter “R” was designated 01010, etc.
Later, as is known, computer symbols, including modern personal ones, began to occupy an 8-bit code (byte). Their number can reach 256 different characters (28).
His first article, “Intelligent Machinery,” in the form of a report from the National Physical Laboratory, was published in 1948 year and then in 1950 In the same year, his seminal article “Computing Machinery and Intelligence” was published in the English magazine “Mind”. It was published in Russian translation under the title “Can a Machine Think?” And today Turing’s analysis of this problem “remains perhaps the best of all, worth reading for anyone who wants to understand the essence of the matter.”
I'm going to look at the question “Can machines think?” - Turing begins the article with these words, but soon he replaces the original formulation of the question with a completely different one, in which the “thinking” of the machine is considered in technical terms. As a criterion for assessing the mental activity of a machine, Turing proposes to use its actions during the “imitation game”. This “game” was later called the Turing test.
In the modern understanding, the Turing test is interpreted as follows: if a machine is capable of imitating behavior that an expert examiner cannot distinguish from the behavior of a person with mental abilities (in Turing, the subjects - a person and a machine are separated from the expert examiner asking questions, by the walls of rooms and communicate through telegraph), then the machine also has these abilities.
Many of his colleagues remember Turing as a person with unconventional views and quirks of character. There were legends about his eccentricities. While living in Cambridge, he never set his watch by time signals, but calculated the time in his head, noting the position of a particular star.
At Bletchley Park, at the beginning of June each year, he suffered from severe attacks of hay fever (allergies), and then he rode his bicycle to work wearing a gas mask to escape the pollen. His bicycle had a defect: the chain would fall off at regular intervals. Instead of fixing it, he counted the number of pedal revolutions in order to get off the bike in time to adjust the chain. He tied his mug to the heating radiator with a chain, as I. Good recalls, so that it would not be stolen.
One day, Turing, having learned about the fall in the value of the English pound, melted the available silver coins and buried the ingot in the park, but then forgot where exactly. Turing was a good athlete. After the war, feeling the need for physical release, he ran a long distance and found that he was successful at it. He then won his club's three-mile and ten-mile races, both times in record time, and 1947 took fifth place in the marathon.
Everything collapsed literally in one day. In 1952, Turing's apartment was robbed. During the investigation, it turned out that this was done by one of his sexual partner’s friends. The scientist, in general, never hid his “non-traditional sexual orientation,” but he also did not behave provocatively. However, the theft scandal received widespread publicity, and as a result, charges of “indecent conduct” were brought against Turing himself. On March 31, 1953, the trial took place. The sentence implied a choice: either imprisonment or injections of the female hormone estrogen (a method of chemical castration). He chose the latter.
On June 8, 1954, Alan Matheson Turing was found dead in his home. He committed suicide by poisoning himself with potassium cyanide.
Turing injected the cyanide solution into the apple. Having bitten it, he died. In a few days he would have turned 42 years old.
Modern mathematicians, programmers and computer engineers are familiar with the name Alan Turing from their student days: they all had to study the “Turing machine” - the “foundation of the fundamentals” of the theory of algorithms. Not a single serious textbook on mathematical logic and computability theory can do without a “Turing machine”.
Behind almost every outstanding scientific discovery there is an amazing story. Behind the "Turing machine" is the life story of a scientific genius - a genius who received worthy recognition only many years after his tragic death.
The role of A. Turing in the history of computer science is by no means limited to the invention of the “Turing machine,” as it may sometimes seem due to the relative paucity of published (in Russian) information about him.
The methodological development of the lesson discussed in this publication is intended for study in grade 10 when considering the thematic block “ Algorithm. Algorithm executors».
In a lesson on the topic " “Accompanied by a multimedia presentation, the children will get acquainted with its structure, study the principle of operation and learn how to build a program for a Turing machine. The lesson material allows you to develop the algorithmic thinking of high school students and the ability to formalize.
By type, this lesson is combined, in which the study of new material is consolidated in the process of solving problems on the topic. The author of the development proposes to use a partial search method of teaching, when the thinking process becomes productive with the consistent direction and control of the teacher.
Description of the course of the lesson on the Turing machine
At the stage of organizing the class, the teacher sets the children up for work, formulates the topic of the lesson and talks about the English Alan Turing, who significantly influenced the development of computer science as a science.
As a warm-up at the next stage of the lesson, schoolchildren solve a logic problem followed by a test at the board. It is important to pay attention to the ability to create a reasoning algorithm.
Having dealt with the problem in the warm-up, we will update the previously covered theoretical material about the algorithm and algorithm executors. To do this, the author of the development proposes to conduct a frontal survey on the following questions:
What is an algorithm called and who is it intended for?
What properties does the algorithm have?
Who is capable of appearing as an executor of the algorithm?
Name the basic concepts of a Turing machine.
Demonstrate the main properties of algorithms using the example of a Turing machine.
Examples of Turing machines - theoretical part
Before starting to solve problems on the topic, in the theoretical part we provide a description of the Turing machine. We draw the class's attention to two components of any of these machines:
1) the tape is unlimited and divided into cells;
2) a program-controlled head that reads information and is called an automatic machine.
Replace one letter of the alphabet contained in a visible memory cell with another;
Shift to the right or left with an interval of one cell or remain in the same place;
Change your own internal state.
Solving problems using Turing machines
The next stage of the lesson involves immersion in the practical part of the lesson and solving problems on the topic. The teacher tells you that you need to try to imitate a device like a calculator using a Turing machine. In total, two tasks are offered, the analysis of which takes place accompanied by presentation slides:
Task 1.
A Turing machine tape contains some decimal number. You need to add 1 to this number ( unit). In this case, the machine looks at a certain number corresponding to the input number.
WHO? A Turing machine is a mathematical (imaginary) machine, not a physical machine. It is the same mathematical object as a function, derivative, integral, etc. WHAT? Alan Mathieson Turing is an English mathematician, logician, and cryptographer. In 1937, he proposed a clarification of the concept of an algorithm as a process that can be performed by a special machine, later called a Turing machine. The concept of a “Turing machine” was formulated 9 years before the appearance of the first computer.
Structure of a Turing machine Tape Reading head Internal state Reading symbol Tape: Potentially infinite; One cell contains one character; An empty cell is filled with the symbol a 0. Head: At any time, it is in only one internal state; Initial state – q 1 ; The final state is q 0.
Example of a Turing machine QA QA q1q1 q2q2 q3q3 0q 1 0Lq 3 1Rq 1 0L 1q 2 0Lq 2 1Lq 3 1R q00q00q 2 Lq 3 R Consider the operation of a Turing machine having the following program: q q q q q q q q q q q q q q q q q q q … … … T f(a,b) = a + b
For what? Turing's thesis: To find the values of a function if and only if there is some algorithm when there is a Turing machine that calculates this function. This thesis cannot be strictly proven by mathematical methods, but so far it has not been possible to come up with a computable function that could not be programmed in the form of a Turing machine. Conclusions: The Turing machine is a mathematically rigorous analogue of the concept of “algorithm”. The principle of operation of the Turing machine underlies all modern computers.
