Algorithmic presentation machines. Turing machine

The methodological development of the lesson, which will be discussed in this publication, is intended for study in grade 10 when considering the thematic block " Algorithm. Algorithm executors».

In the 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 material of the lesson allows to develop the algorithmic thinking of high school students, 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 about 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, students decide logical task followed by a check at the board. It is important to pay attention to the ability to draw up a reasoning algorithm.

Having dealt with the warm-up task, we update the previously passed theoretical material about the algorithm and the executors of the algorithms. To do this, the author of the development proposes to conduct a frontal survey on the following questions:

What is called an algorithm and who is it intended for?

What properties does the algorithm have?

Who is able to appear as the executor of the algorithm?

What are the basic concepts of the Turing machine?

Demonstrate the main properties of algorithms using an example of a Turing machine.

Examples of Turing machines - theoretical part

Before proceeding with the solution of problems on the topic, in the theoretical part we give a description of the Turing machine. We draw the attention of the class 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 called an automaton.

Replace one letter of the alphabet contained in the visible memory cell with another;

Shift to the right or left with an interval of one cell, or stay in the same place;

Change your own inner 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 says that with the help of a Turing machine, it is necessary to try to simulate a device similar to a calculator. In total, two tasks are proposed, the analysis of which takes place accompanied by presentation slides:

Objective 1. The Turing machine tape contains some decimal number. It is necessary to add to this number 1 ( unit). The automaton in this case examines a certain digit corresponding to the input number.

Definition of a Turing machine

A Turing machine is an abstract executor that implements an algorithmic process designed to refine the concept of an algorithm. It is a mathematical object, not a physical machine. Proposed by Alan Turing in 1936, the Turing Machine is a rigorous mathematical construction, a mathematical apparatus designed to solve certain problems.

Structure and description of a Turing machine A Turing machine consists of: an endless tape divided into cells; carriage (reading and writing head); programmable machine (program in the form of a table). The machine “sees” only one cell each time. Depending on which letter it sees, as well as depending on its state q, the automaton can perform the following actions: write a new letter to the observed cell; perform a shift along the tape one cell to the right / left or remain motionless; go to a new state.

1) External alphabet A = (a 0, a 1,…, a n) 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 structure

2) Internal alphabet Q = (q 0, q 1,…, qm), (P, L, N!) At any moment of time, the Turing machine is in one of the states q 0, q 1,…, qm In this case: q 1 - initial state (the machine starts work) q 0 - final state (the machine has finished work) Symbols (P, L, N!) - shift symbols (right, left, in place) Turing machine structure

Types of Turing machine commands Write a new letter to the observed cell Shift along the tape one cell to the right / left or stay in place (P, 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 a symbol change Indication of a carriage shift Indication of a change in internal state

3) External memory (tape) The machine has a tape divided into cells, each of which can contain only one letter. Turing machine structure

3) External memory (tape) Turing machine structure An empty cell contains a 0. At each moment of time, a finite number of non-empty letters are recorded on the tape. The tape is finite, but at any moment it is supplemented with cells on the left and right to record new non-empty characters. This is in line with 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 character written in the cell.In one cycle of work, the carriage is shifted one cell (right, left) or remains in place. The device of the Turing machine

5) Functional diagram (program) The machine program consists of instructions: Turing machine structure For each pair (q i, a j) the machine program must contain one instruction (deterministic Turing machine)

By the beginning of the machine operation, the initial data set is fed to the tape in the form of the word  Description of the Turing machine operation We will say that a non-empty word  in the alphabet A \ (a 0) is perceived by the machine in its standard position if: - it is given in consecutive cells of the tape, - all other cells are empty - the car is looking at the rightmost cell of those containing the word 

Description of the operation of the Turing machine The standard position is called the initial (final) position if the machine that perceives the word in the standard position is in the initial state q 1 (stop state q 0)

Being in a non-final state, the machine makes a step, which is determined by the current state q i and the monitored symbol a j Description of the Turing machine operation

Description of the operation of the Turing machine In accordance with the command qiaj  qkal X, the following actions are performed: 1) The contents of the observed cell aj are erased and the symbol al is written into it (which may coincide with aj) 2) The machine enters a new state qk (it may coincide with the state qi) 3) The carriage moves in accordance with the controlled character X  (P, L, N!)

When the machine enters the final state q 0, its operation stops The tape contains the result of the algorithm operation - the word  in the alphabet A \ (a 0) Description of the Turing machine operation

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 is observing the symbol a l on the tape -  1 and  2 - this is 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 stop 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 work on this input word, sooner or later it reaches one of the stopping cells. How has the example program changed? a 0 0 1 q 1 1P q 1 0P q 1 1P q 1 a 0 0 1 q 1 1H q 0 0P q 1 1P q 1

An 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 H! b L q 1 a L q 1 c 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 A Turing machine adds one to the number on the tape. The input word consists of integer digits decimal written in consecutive cells on a tape. At the initial moment, the car is located opposite the rightmost digit of the number. a 0 0 1 2 3 4 ... 7 8 9 q 1 1H q 0 1H q 0 2H q 0 3H q 0 4H q 0 5H q 0 ... 8H q 0 9H q 0 0L q 1

Implement the proposed algorithm The tape of the Turing machine contains a sequence of symbols "+". The Turing machine replaces every second symbol "+" with "-". Replacement starts at the right end of the sequence. The automaton in state q 1 looks at one of the symbols of the specified sequence. a 0 + - q 1 a 0 L q 2 + P q 1 q 2 a 0 H! + Л q 3 q 3 а 0 Н! - Л q 2 q 1 - the machine is looking for the right end of the number; q 2 - skips the "+" sign, upon reaching the end of the sequence - stop; q 3 - 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 a 0

Solution 2) The machine goes into a new state q 2

Solution 3) The carriage moves to the left

Solution Complete detailed solution

Solution Complete detailed solution

Solution Solution written with configurations (in 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. Practical problem book and solutions. - SPb .: Lan, 1999 .-- 288 p. Ilinykh A.P. Theory of algorithms. Tutorial... - Yekaterinburg, 2006 .-- 149 p.

People can behave differently in the same situations, and in this they are fundamentally different from machines.

Alan Turing

Alan Mathison Turing Alan Mathison Turing (English Alan Mathison Turing; June 23, 1912 - June 7, 1954) - English mathematician, logician, cryptographer, who had a significant impact on the development of computer science. Commander of the Order of the British Empire (1945), Fellow of the Royal Society of London (1951). The abstract computing "Turing Machine" proposed by him in 1936, which can be considered a general-purpose computer model, made it possible to formalize the concept of an algorithm and is still used in many theoretical and practical studies. Scientific works A. Turing is a recognized contribution to the foundations of computer science (and, in particular, the theory of artificial intelligence).

Time of War During World War II, Alan Turing worked at the Government Codes and Ciphers School located in Bletchley Park, where the work on cracking ciphers and Axis codes was concentrated. He led the Hut 8 group, which is responsible for cryptanalizing messages from the German Navy. Turing developed a number of hacking techniques, including the theoretical basis for the Bombe, the machine used to hack the German Enigma encryption device.

Turing Machine Within weeks of arriving at Blatchley Park, Turing wrote specifications for an electromechanical machine that could help break the Enigma more effectively than the Polish cryptological bomb. The Turing Machine, with improvements suggested by the mathematician Gordon Welchman, has become an essential tool for deciphering Enigma messages. The car was named Bombe. The machine searched for possible settings used to encrypt messages (rotor order, rotor position, patch panel connections) based on known plaintext. For each possible rotor setting (which had 1019 states or 1022 in the modification used on submarines), the machine made a series of logical assumptions based on the plain text (its content and structure). Then the machine identified the contradiction, discarded the set of parameters and moved on to the next one. Thus, most of the possible sets were eliminated and only a few options remained for careful analysis. The first vehicle entered service on March 18, 1940. Enumeration of keys was carried out due to the rotation of mechanical drums, accompanied by a sound similar to the ticking of a clock.

Colossus In July 1942, Turing took part in deciphering the Lorenz code used by the Germans to transmit messages to high command. "Lorenz" was much more complex than "Enigma" and could not be deciphered by existing methods. Turing suggested using vacuum tubes in the design of the decoder and brought in the team T. Flowers, an experienced electronic engineer. As a result of the joint efforts of mathematicians and engineers, "Colossus" was developed - one of the first computers in the world. By 1944, with the help of the Colossus, the Lorenz code had been cracked, which allowed the Allies to read all the correspondence of the highest German leadership. According to some estimates, this brought the defeat of Germany closer by several years.

Early Computers and the Turing Test From 1945 to 1947, Turing lived in Richmond and worked on the ACE (Automatic Computing Engine) at the National Physics Laboratory. On February 19, 1946, he presented what could be called the first detailed description of a computer with a program stored in memory. Von Neumann's unfinished work "First Draft EDVAC Report" (1945) preceded it, but was much less detailed, and according to the head of the mathematics department of the National Physics Laboratory - John Wurmsley: it contains a number of ideas that belong to Dr. Turing. Although the construction of the ACE was feasible, the secrecy surrounding Blatchley Park led to delays in the start of work, which disappointed Turing. Towards the end of 1947, he returned to Cambridge for a year's leave during which he productively worked on Intelligent Machinery, which had not been published during his lifetime. While Alan Turing was at Cambridge, the ACE Pilot was built in his absence. He performed his first program on May 10, 1950. Though full version ACE was never built, some computers had a lot in common with it, for example DEUCE and Bendix G-15

In 1948, Alan Turing received the title of Reader from the Mathematics Department of the University of Manchester. There, in 1949, he became director of the Computer Laboratory, where the programming of the Manchester Mark I was concentrated. At the same time, Turing continued to work on more abstract mathematical problems, and in his work "Computing Machinery and Intelligence" Mind ", October 1950) he turned to the problem of artificial intelligence and proposed an experiment that later became known as the Turing test. His idea was that a computer can be considered to "think" if the person interacting with it cannot distinguish the 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 a child and then teach it. CAPTCHA based on the reverse Turing test is widespread on the Internet. In 1948, Alan, together with his former colleague David Champernovn (English), began writing a chess program for a computer that did not yet exist. In 1952, without a suitable device for its execution, Turing played a game in which he simulated the actions of a machine, making one move every half an hour. The game was recorded and, as a result, the program lost to Turing's colleague Alec Glini, but won the game over Champernovna's wife. Turing also invented the LU expansion method in 1948, which is used today to solve equations.

Slide 2

Introduction

The concept of an algorithm. An algorithm is an exact prescription that determines the computational process going from variable input data to the desired result (Markov A.A.) Algorithm properties: 1) Discreteness. 2) Certainty. 3) Effectiveness. 4) Mass character.

Slide 3

Turing machine mathematical model

A Turing Machine (MT) is a mathematical model of an idealized digital computing machine. The device of the Turing machine. Ribbon. Reading head. Control device. Inner memory.

Slide 4

ribbon

Only one symbol (letter) from the external alphabet A = (˄, a1, a2,…, an-1), 2≥n can be written into cells at a discrete moment in time. An empty cell is denoted by the symbol ˄, and the symbol ˄ itself is called empty, while the rest of the characters are said to be non-empty.

Slide 5

Reading head

The head can read the contents of a cell and write into it a new character from the alphabet A. In one cycle of work, it can move only one cell to the right (P), left (L), or remain in place (H).

Slide 6

Inner memory

The internal memory of the machine is a certain finite set of internal states Q = (q0, q1,…, qm), m≥ 1. We assume that the cardinality | Q | ≥2. Two states of the machine are of particular importance: q1 is the initial internal state (there can be several initial internal states), q0 is the final state or stop state (the final state is always one). At each moment of time, the MT is characterized by the position of the head and the internal state.

Slide 7

Control device

Performs the following actions: Changes the character ai read at time t to a new character aj (in particular, leaves it unchanged, that is, ai = aj); Moves the head in one of the following directions: N, L, R; Changes the internal state of the machine qi existing at time t to the new qj, in which the machine will be at time t +1. Such actions of the control device are called a command, which can be written in the form: qiaiajDqj

Slide 8

Turing machine operation

The operation of the machine is completely determined by the task at the first (initial) moment: Words on the tape, that is, the sequence of characters written in the cells of the tape (a word is obtained by reading these characters along the cells of the tape from left to right); Head positions; Internal state of the machine.

Slide 9

If at the initial moment the words a1, a2, ˄, a1, a1 are written on the tape, then the initial configuration will be as follows: The operation of the Turing machine consists in the sequential application of commands, moreover, the use of one or the command is determined by the current configuration. So in the example above, the command with the left side q1a1 should be applied. The result of the machine's operation is the word that will be recorded on the tape in the final configuration, i.e., in the configuration in which the internal state of the machine is q0.

Slide 10

Examples of Turing machines

Example 1. Construct a Turing machine T1 that is applicable to all words with an outer alphabet (a, b) and does the following: any word x1, x2 ... xn, where xi = a or xi = b (i = 1, 2 ... n) transforms into a word x2, ... xn, x1, i.e., starting to work with the word x1, x2 ... xn on the tape in the initial configuration, the machine will stop, and in the final configuration, on some section of the tape, the word x2, ... xn, x1 will be written, and all other cells of the tape (if any) will be empty.

Slide 11

Solution: For the outer alphabet of the machine T1 we take the set A = (˄, a, b), and for the inner one - Q = (q0, q1, q2, q3). The commands are defined as follows: q1a ˄Пq2, q1b ˄Пq3, qiy ˄PPi, where yϵ (a, b), i = 2, 3; q2˄ aHq0, q3˄ bHq0 Consider the operation of the machine T1 on the word ba. In the operation of the machine on the word ba, the initial configuration is as follows:

A shorter record of this sequence of configurations, that is, the process of the machine's operation, will be: Thus, the word bbabb is transformed by the machine into the word babbb.

View all slides