FEDERAL AGENCY FOR EDUCATION STATE EDUCATIONAL INSTITUTION OF HIGHER PROFESSIONAL EDUCATION "VORONEZH STATE UNIVERSITY" T.K. Katsaran, L.N. Stroeva TURING MACHINE AND RECURSIVE FUNCTIONS Textbook for universities Publishing and Printing Center of Voronezh State University 2008 Approved by the scientific and methodological council of the faculty of PMM on May 25, 2008, protocol No. 9 Reviewer Doctor of Technical Sciences, Prof. Department of Mathematical Methods for Operations Research T.M. Ledeneva The textbook was prepared at the Department of Nonlinear Oscillations, Faculty of Mechanical Mathematics, Voronezh State University. Recommended for 1st year students of the Faculty of Applied Mathematics and Mathematics of VSU, Starooskolsky and Liskinsky branches of VSU. For specialty 010500 – Applied mathematics and computer science INTRODUCTION The word “algorithm” comes from algorithmi – the Latin spelling of the name of the Uzbek mathematician and astronomer who lived in the 8th–9th centuries (783–850), Muhammad ben Musa al-Khwarizmi. The greatest mathematician from Khorezm (a city in modern Uzbekistan) was known under this name in Medieval Europe. In his book “On Indian Counting,” he formulated the rules for writing natural numbers using Arabic numerals and the rules for operating on them. Then the concept of an algorithm began to be used in a broader sense and not only in mathematics. For both mathematicians and practitioners, the concept of an algorithm is important. Thus, we can say that an algorithm is a precise prescription for performing a certain system of operations in a certain order to solve all problems of the same type, defining a sequence of actions that ensures obtaining the required result from the initial data. Note that this is not a definition of the concept “algorithm”, but only its description, its intuitive meaning. The algorithm can be designed to be executed either by a person or by an automatic device. This idea of ​​an algorithm is not rigorous from a mathematical point of view, since it uses such concepts as “exact instructions” and “initial data”, which, generally speaking, are not strictly defined. A feature of any algorithm is its ability to solve a certain class of problems. For example, this could be an algorithm for solving systems of linear equations, finding the shortest path in a graph, etc. Creating an algorithm, even the simplest one, is a creative process. It is available exclusively to living beings, and for a long time it was believed that only to humans. Another thing is the implementation of an existing algorithm. It can be entrusted to a subject or object who is not obliged to delve into the essence of the matter, and perhaps is not able to understand it. Such a subject or object is usually called a formal performer. An example of a formal performer is an automatic washing machine, which strictly performs the actions prescribed to it, even if you forgot to put powder in it. A person can also act as a formal performer, but first of all, various automatic devices, including a computer, are formal performers. Each algorithm is created with a very specific performer in mind. Those actions that the performer can perform are called his permissible actions. The set of permissible actions forms a system of performer commands. The algorithm must contain only those actions that are permissible for a given performer. Therefore, several general properties of algorithms are usually formulated to distinguish algorithms from other instructions. The algorithm must have the following properties. Discreteness (discontinuity, separateness) – the algorithm must represent the process of solving a problem as a sequential execution of simple (or previously defined) steps. Each action provided by the algorithm is executed only after the previous one has completed execution. Certainty - each rule of the algorithm must be clear, unambiguous and leave no room for arbitrariness. Thanks to this property, the execution of the algorithm is mechanical in nature and does not require any additional instructions or information about the problem being solved. Efficiency (finiteness) – the algorithm should lead to solving the problem in a finite number of steps. 4 Mass scale - the algorithm for solving the problem is developed in a general form, that is, it should be applicable for a certain class of problems that differ only in the initial data. In this case, the initial data can be selected from a certain area, which is called the area of ​​applicability of the algorithm. Algorithm theory is a branch of mathematics that studies the general properties of algorithms. There are qualitative and metric theories of algorithms. The main problem of the qualitative theory of algorithms is the problem of constructing an algorithm that has specified properties. This problem is called an algorithmic problem. Metric theory of algorithms examines algorithms in terms of their complexity. This branch of the theory of algorithms is also known as algorithmic complexity theory. When searching for solutions to some problems, it took a long time to find the appropriate algorithm. Examples of such problems are: a) indicate a method according to which, for any predicate formula, in a finite number of operations one can find out whether it is identically true or not; b) is the Diophantine equation (an algebraic equation with integer coefficients) solvable in integers? Since it was not possible to find algorithms for solving these problems, the assumption arose that such algorithms do not exist at all, which was proven: the first problem was solved by A. Church, and the second by Yu.V. Matiyasevich and G.V. Chudnovsky. It is in principle impossible to prove this using the intuitive concept of an algorithm. Therefore, attempts have been made to give a precise mathematical definition of the concept of an algorithm. In the mid-30s of the twentieth century, S.K. Kleene, A.A. Markov, E. Post, A. Turing, A. Church and others have proposed various mathematical definitions 5 of the concept of algorithm. Subsequently, it was proven that these different formal mathematical definitions are in some sense equivalent: they calculate the same set of functions. This suggests that the main features of the intuitive concept of an algorithm appear to be correctly captured in these definitions. Next, we consider a mathematical refinement of the algorithm proposed by A. Turing, which is called a Turing machine. 6 1. TURING MACHINE § 1. Mathematical model of the Turing machine The idea of ​​​​creating a Turing machine, proposed by the English mathematician A. Turing in the thirties of the 20th century, is associated with his attempt to give a precise mathematical definition of the concept of an algorithm. A Turing machine (MT) is a mathematical model of an idealized digital computer. A Turing machine is the same mathematical object as a function, derivative, integral, group, etc. Just like other mathematical concepts, the concept of a Turing machine reflects objective reality and models certain real processes. To describe the MT algorithm, it is convenient to imagine a device consisting of four parts: tape, read head, control device and internal memory. 1. The tape is assumed to be potentially infinite, divided into cells (equal cells). If necessary, an empty cell is attached to the first or last cell in which the symbols are located. The machine operates in time, which is considered discrete, and its moments are numbered 1, 2, 3, …. At any moment the tape contains a finite number of cells. Only one symbol (letter) from the external alphabet A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 can be written into cells at a discrete time. An empty cell is designated by the symbol L, and the symbol L itself is called empty, while the remaining symbols are called non-blank. In this alphabet A, the information that is supplied to the MT is encoded in the form of a word (a finite ordered set of symbols). The machine “processes” information presented in the form of a word into a new word. 2. The reading head (a certain reading element) moves along the tape so that at each moment of time it views exactly one cell of the tape. The head can read the contents of a cell and write a new character from the alphabet A into it. In one cycle of operation, it can move only one cell to the right (R), left (L) or remain in place (N). Let us denote the set of movements (shifts) of the head D = (P, L, N). If at a given moment t the head is in the outermost cell and moves to the missing cell, then a new empty cell is added, above which the head will be at the moment t + 1. 3. The internal memory of the machine is a certain finite set of internal states Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 . We will assume that the power |Q | ³ 2. Two states of the machine have a special meaning: q1 is the initial internal state (there can be several initial internal states), q0 is the final state or stop state (there is always one final state). At each moment of time, the MT is characterized by the position of the head and internal state. For example, under the cell above which the head is located, the internal state of the machine is indicated. ¯ a2 a1 L a2 a3 q1 4. At each moment t, the control device, depending on the symbol on the tape being read at that moment and the internal state of the machine, performs the following actions: 1) changes the symbol ai read at the moment t to a new symbol a j (in particular, leaves it unchanged, i.e. ai = a j); 2) moves the head in one of the following directions: N, L, R; 3) changes the internal state of the machine 8 qi existing at moment t to a new q j in which the machine will be at time t +1 (it may be that qi = q j). Such actions of the control device are called a command, which can be written in the form: qi ai ® a j D q j , (1) where qi is the internal state of the machine at the moment; a i – the symbol being read at this moment; a j – the symbol to which the symbol a i changes (can be ai = a j); the symbol D is either N, or L, or P and indicates the direction of movement of the head; q j is the internal state of the machine at the next moment (maybe qi = q j). The expressions qi ai and a j D q j are called the left and right sides of this command, respectively. The number of commands in which the left-hand sides are pairwise distinct is a finite number, since the sets Q \ (q 0 ) and A are finite. There are no commands with identical left-hand sides, i.e. if the machine program T contains the expressions qi ai ® a j D q j and qt at ® ak D qk , then qi ¹ qt or ai ¹ at and D O (P, L, N). The set of all instructions is called a Turing machine program. The maximum number of commands in a program is (n + 1) x m, where n + 1 = A and m + 1 = Q. It is believed that the final state of the command q0 can only appear on the right side of the command, the initial state q1 can appear on both the left and the right side of the command. Executing one command is called a step. The computation (or operation) of a Turing machine is a sequence of steps one after another without skipping, starting with the first. So, MT is given if four finite sets are known: the external alphabet A, the internal alphabet Q, the set D of head movements and the machine program, which is a finite set of commands. 9 § 2. Operation of a Turing machine The operation of the machine is completely determined by the task at the first (initial) moment: 1) words on the tape, i.e., a sequence of symbols written in the cells of the tape (a word is obtained by reading these symbols across the cells of the tape from left to right) ; 2) head position; 3) the internal state of the machine. The combination of these three conditions (at the moment) is called configuration (at the moment). Typically, at the initial moment, the internal state of the machine is q1, and the head is either above the first left or first right cell of the tape. A given word on the tape with initial state q1 and head position above the first word is called the initial configuration. Otherwise, we say that the Turing machine is not applicable to a word of initial configuration. In other words, at the initial moment the configuration is representable in the following form: on a tape consisting of a certain number of cells, in each cell one of the symbols of the external alphabet A is written, the head is located above the first left or first right cell of the tape and the internal one. the machine's position is q1. The resulting word on the tape and head position resulting from the implementation of this command is called the final configuration. For example, if at the initial moment the word a1La 2 a1a1 is written on the tape, then the initial configuration will look like: a1 a2 L a1 a1 q1 (under the cell above which the head is located, the internal state of the machine is indicated). 10

Topic “Turing Machine” in a school computer science course

I.N. Falina,
Moscow

In many computer science textbooks, when studying the concept and properties of an algorithm, there are phrases with the following content: “... there are many different ways to write the same algorithm, for example, writing in the form of text, writing in the form of a flowchart, writing in some algorithmic language, representation of an algorithm in the form of a Turing machine or a Post machine...” Unfortunately, these types of phrases are the only ones that mention a Turing machine. Without a doubt, the volume of hours devoted to the study of algorithms does not allow us to also include in this topic the study of ways to write an algorithm in the form of a Turing machine. But this topic is extremely interesting, important and useful for schoolchildren, especially those interested in computer science.

The topic “Turing Machine” can be studied in grades 8–11 as part of the topic “Information Processes. Information processing”, in elective classes, in the system of additional education, for example, in schools for young programmers. The study of this topic can be accompanied by computer support if the teacher has a software simulator “Turing Machine”. In advanced programming classes, students can independently write a Turing Machine program. As part of this article, we offer you a workshop on solving problems on the topic “Turing Machine”. Theoretical material on this topic has been published more than once on the pages of the Informatics newspaper, for example, in No. 3/2004, an article by I.N. Falina “Elements of the theory of algorithms”.

A Turing machine is a strict mathematical construction, a mathematical apparatus (similar, for example, to the apparatus of differential equations) created to solve certain problems. This mathematical apparatus was called a “machine” for the reason that, in the description of its constituent parts and operation, it is similar to a computer. The fundamental difference between a Turing machine and computers is that its storage device is an infinite tape: in real computers, the storage device can be as large as you like, but it must be finite. A Turing machine cannot be realized precisely because its tape is infinite. In this sense, it is more powerful than any computing machine.

Every Turing machine has two parts:

1)unlimited round trip ribbon, divided into cells;

2) machine(read/write head controlled by software).

Each Turing machine is associated with two final alphabets: alphabet of input symbols A = (a 0 , a 1 , ..., a m ) and alphabet of states Q = (q 0 , q 1 , ..., q p ). (Different Turing machines may have different alphabets associated with them A And Q.) The state q 0 is called passive. It is believed that if the machine gets into this state, then it has finished its work. State q 1 is called initial. While in this state, the machine begins its work.

The input word is placed on the tape one letter at a time in consecutive cells. To the left and right of the input word there are only empty cells (in the alphabet A always includes an empty letter A 0 is a sign that the cell is empty).

The machine can move along the tape to the left or right, read the contents of the cells and write letters into the cells. Below is a schematic drawing of a Turing machine, whose automaton examines the first cell with data.

The machine “sees” only one cell each time. Depending on which letter ai he sees, and also depending on his condition qj The machine 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.

That is, a Turing machine has three types of operations. Each time for the next couple ( q j, a i) a Turing machine executes a command consisting of three operations with certain parameters.

The Turing machine program is a table with a command written in each cell.

Cell ( q j, a i) is determined by two parameters - the alphabet symbol and the state of the machine. The command is an indication: where to move the read/write head, what character to write to the current cell, what state the machine should go to. To indicate the direction of movement of the machine, we use one of three letters: “L” (left), “P” (right) or “N” (stationary).

After the machine executes the next command, it goes into the state q m(which may in a particular case coincide with the previous state q j). The next command should be found in m th row of the table at the intersection with the column a l(letter a l the machine sees after the shift).

Let's agree that when the tape contains an input word, then the machine is located against some cell in the state q 1. During operation, the automaton will jump from one cell of the program (table) to another until it reaches the cell in which it is written that the automaton should go into the state q 0 . These cells are called stop cells. Having reached any such cell, the Turing machine stops.

Despite its simple design, a Turing machine can perform all possible transformations of words, thereby implementing all possible algorithms.

Example. You need to build a Turing machine that adds one to a number on a tape. The input word consists of the decimal integer digits written into consecutive cells on the tape. At the initial moment, the machine is located opposite the rightmost digit of the number.

Solution. The machine must add one to the last digit of the number. If the last digit is 9, then replace it with 0 and add one to the previous digit. A program for a given Turing machine might look like this:

In this Turing machine q 1 - digit change state, q 0 - stop state. If you can q l the machine sees the number 0..8, then it replaces it with 1..9, respectively, and goes into the state q 0, i.e. the car stops. If he sees the number 9, then he replaces it with 0, moves to the left, remaining in the state q l. This continues until the machine encounters a number less than 9. If all the numbers were equal to 9, then it will replace them with zeros, write 0 in place of the highest digit, move to the left and write 1 in an empty cell. Then it will go into the state q 0, i.e. will stop.

Practical tasks

1. The Turing machine tape contains a sequence of symbols “+”. Write a program for a Turing machine that replaces every second “+” symbol with a “–”. The replacement starts from the right end of the sequence. The machine is able q 1 looks at one of the characters in the specified sequence. In addition to the table program itself, describe in words what is performed by the machine in each state.

2. Given a number n in the octal number system. Design a Turing machine that increments a given number n on 1. The machine is able q 1 looks at a certain digit of the input word. In addition to the table program itself, describe in words what is performed by the machine in each state.

3. Given the decimal notation of a natural number n> 1. Develop a Turing machine that would reduce a given number n on 1. The machine is able q 1 looks at the right digit of the number. In addition to the table program itself, describe in words what is performed by the machine in each state.

4. Given a natural number n> 1. Develop a Turing machine that would reduce a given number n by 1, while the most significant digit in the output word should not be 0. For example, if the input word was “100”, then the output word should be “99”, not “099”. The machine is able q 1 looks at the right digit of the number. In addition to the table program itself, describe in words what is performed by the machine in each state.

5. Given an array of opening and closing parentheses. Build a Turing machine that would remove pairs of mutual parentheses, i.e. located in a row “()”.

For example, given “) (() (()”, you need to get “) . . . ((”.

The machine is able q

6. Given a string of letters “ a" And " b" Develop a Turing machine that will move all the letters “ a” to the left, and the letters “ b” - to the right side of the line. The machine is able q 1 looks at the leftmost character of the line. In addition to the table program itself, describe in words what is performed by the machine in each state.

7. On the Turing machine tape there is a number written in the decimal number system. Multiply this number by 2. The machine is able q 1 looks at the leftmost digit of the number. In addition to the table program itself, describe in words what is performed by the machine in each state.

8. Given two natural numbers m And n, presented in the unary number system. Matching character sets are “|” separated by an empty cell. The machine is able q 1 looks at the rightmost character of the input sequence. Develop a Turing machine that will leave a sum of numbers on a tape m And n. In addition to the table program itself, describe in words what is performed by the machine in each state.

9. Given two natural numbers m And n, presented in the unary number system. Matching character sets are “|” separated by an empty cell. The machine is able q 1 looks at the rightmost character of the input sequence. Develop a Turing machine that will leave a difference between numbers on the tape. m And n. It is known that m> n. In addition to the table program itself, describe in words what is performed by the machine in each state.

10. There is a decimal number on the Turing machine tape. Determine whether this number is divisible by 5 without a remainder. If it is divisible, then write the word “yes” to the right of the number, otherwise - “no”. The machine examines a certain digit of the input number. In addition to the table program itself, describe in words what is performed by the machine in each state.

Able q 1 machine searches for the right end of the number, able q 2 - skips the “+” sign, when reaching the end of the sequence - stops. Able q 3, the machine replaces the “+” sign with the “–” sign, and when it reaches the end of the sequence it stops.

The solution to this problem is similar to the example discussed above.

State q 1 - we decrease the lowest (next) digit by 1. If it is not equal to zero, then immediately stop after the decrease; if the lowest digit is 0, then we write 9 instead, shift to the left and perform the subtraction again. In the cage [ a 0 , q 1 ] a Turing machine will never hit, so it can be left unfilled.

Task 4 (complication of task 3)

State q 1 - we decrease the minor (next) digit by 1. If it is greater than 1, then after the reduction we stop immediately, but if the minor digit is 0, then we write 9 instead, shift to the left and perform the subtraction again. If the digit being reduced is 1, then we write 0 instead and go to the state q 2 .

State q 2 - after writing “0” in any position, it is necessary to analyze whether this zero is the most significant digit (i.e., whether it is to the left of it in the output word record a 0).

State q 3 - if the recorded “0” is the most significant digit, then it must be removed from the output word record.

Those cells that the Turing machine never gets into are left empty.

State q 1: if “(” is encountered, then shift to the right and go to the state q 2 ; if you met “ a 0”, then stop.

State q 2: analysis of the symbol “(” for pairing, in case of pairing they should see “)”. If it’s a steam room, then return to the left and go to the state q 3 .

State q 3: first erase “(”, then “)” and go to q 1 .

Solving this problem usually causes difficulty for schoolchildren. When analyzing the solution to this problem, you can go, for example, in the following way.

Review the following options for input words with your students and ask them to formulate what a Turing machine should do, what the output word looks like, and how these options differ from the point of view of a Turing machine:

aaa ->

a -> the output word matches the input word, we look through the input word until it ends.

bbb -> the output word matches the input word, we look through the input word until it ends.

b -> the output word matches the input word, we look through the input word until it ends.

ab -> the output word matches the input word, we look through the input word until it ends.

Result of the discussion. A Turing machine must “understand” which chain of letters it follows, i.e. it must have at least two states. Let the state q 1 - movement along a chain of letters “ a", A q 2 - state of movement along a chain of letters “ b" Note that the chain can also consist of one letter. If we have reached the end of the line in the state q 1 or q 2, i.e. met a 0 , the machine should stop, we have processed the entire line.

Consider the following options for input words:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

Result of the discussion. The first version of the input word can be processed sequentially as follows: bba -> bbb-> return to the left end of the letter chain “ b” -> abb(replace the first letter in this chain with “ a"). To perform these actions, we will need to introduce two new states and, in addition, clarify the state q 2. Thus, to solve this problem we need to build a Turing machine with the following states:

q 1 - go to the right along the chain of letters “ a" If the chain ends a 0, then go to q 0 ; if it ends with the letter “ b”, then we go to q 2 ;

q 2 - go to the right along the chain of letters “ b” if the chain ends a 0, then go to q 0 ; if ends “ a”, then replace the letter “ a" on " b”, go to the state q 3 (the chain of the species was replaced by a chain of the species);

q 3 - go left along the chain of letters “ b” to its left end. If you met a 0 or “ a”, then we go to q 4 ;

q 4 - replace “ b" on " a” and go to q 1 (we replace the chain of the form with a chain of the form .

Problem 7

state q 1 - search for the right (lowest) digit of a number;

state q 2 - multiplying the next digit of a number by 2 without adding 1 carry;

state q 3 - multiplying the next digit of a number by 2 with the addition of 1 carry.

The Turing machine for this program looks trivially simple - it has only one state. Such a Turing machine performs the following actions: erases the rightmost stroke, looks for a separator (empty cell) and places a stroke in this empty cell, thereby forming a continuous sequence of strokes of length n + m.

However, oddly enough, solving this problem causes great difficulties. Very often, students build a Turing machine that performs cyclic actions: sequentially pushing the right n strokes to the left.

In this case, their program looks like this:

state q 1 - search for separator;

state q 2 - moved the stroke;

state q 3 - check for the end (whether all the strokes have been moved).

The example of this problem clearly shows how often children try to solve a problem in already familiar ways. It seems to me that by offering students problems to construct Turing machines, we develop the ability to find unusual solutions and develop the ability to think creatively!

This task seems quite easy to schoolchildren, but difficulties arise with stopping the Turing machine. Below is one possible version of a Turing machine for this task.

Solution idea (stop condition). There are two initial stroke arrays on the tape.

We begin to erase strokes from the left end of the array m. And one by one we erase the leftmost stroke in the array m and the rightmost stroke in the array n. But before erasing the right stroke in the array n, we check whether it is the only one (i.e. the last one that needs to be erased) or not.

Let us first describe the states of the Turing machine that are necessary to solve our problem, and then create a table program.

State q 1 - search for a separator between arrays of strokes when moving from right to left;

state q 2 - search for the left stroke in the array m;

state q 3 - removing the left stroke in the array m;

state q 4 - search for a separator when moving from left to right;

state q 5 - search for the right stroke in the array n;

state q 6 - checking the uniqueness of this stroke in the array n, i.e. determine whether it was the last one;

state q 7 - if it was the last, then stop, otherwise go to a new cycle of algorithm execution.

When solving this problem, you should pay attention to the correct writing of the alphabet:

A = ( a 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

State q 1 - search for the right end of the number;

state q 2 - analysis of the least significant digit of the number; if it is equal to “0” or “5”, i.e. the number is divisible by 5, then the transition to the state q 3 , otherwise transition to state q 5 ;

state q 3 - write the letter “D” to the right of the word on the tape;

state q 4 - write the letter “A” to the right of the word and stop the machine;

state q 5 - writing the letter “N” to the right of the word;

state q 6 - writing the letter “E” to the right of the word;

state q 7 - write the letter “T” to the right of the word and stop the machine.

Properties of the Turing machine as an algorithm

Using the Turing machine as an example, the properties of algorithms can be clearly seen. Ask students to show that a Turing machine has all the properties of an algorithm.

Discreteness. A Turing machine can go to ( k + 1)th step only after completing To- th step, because exactly To- th step determines what will be ( k + 1)th step.

Clarity. At each step, a symbol from the alphabet is written into the cell, the automaton makes one movement (L, P, N), and the Turing machine goes into one of the described states.

Determinism. Each cell of the Turing machine table contains only one option for an action. At each step, the result is uniquely determined, therefore, the sequence of steps for solving the problem is uniquely determined, i.e. If a Turing machine is given the same input word, then the output word will be the same each time.

Productivity. In terms of content, the results of each step and the entire sequence of steps are uniquely defined; therefore, a correctly written Turing machine will go into the state in a finite number of steps q 0, i.e. in a finite number of steps the answer to the problem question will be obtained.

Mass character. Each Turing machine is defined over all admissible words from the alphabet, this is the property of mass character. Each Turing machine is designed to solve one class of problems, i.e. For each problem, its own (new) Turing machine is written.

FROM THE EDITOR

All the problems given in the article can be solved simply in a notebook by drawing an information strip and a table program. But you can make this process more fun and visual: use a machine implementation - the interpreter of the Post machine and the Turing machine “Algo2000”, created by Radik Zartdinov. The program has an intuitive interface, and its requirements are the most moderate: an IBM PC AT 486 or higher computer, the Windows 95/98/NT operating system.

Let's look in general terms at how “Algo2000” works.

In the program menu, select the item Interpreter and indicate which machine we want to work with (in our case, it is a “Turing machine”).

A Turing machine field will appear in front of us.

Now you need to set the external alphabet, i.e. in line External alphabet indicate which characters are included in it (if the string External alphabet not visible, you need to select a menu item View | External alphabet). Each character can only be specified once. After finishing entering the external alphabet, the first column of the table is formed: it is filled with characters from the external alphabet in the same order. When editing the external alphabet, the table is automatically changed: rows are inserted, deleted or swapped.

Let's not forget that you need to somehow arrange the symbols of the external alphabet into sections of the tape (you can leave all sections empty) and place the carriage opposite one of the sections, i.e. you need to set the program and some state of the machine.

Now you can proceed directly to writing the algorithm for solving the problem. It is specified in the form of a table: characters of the internal alphabet are entered in each column of the top line, and characters of the external alphabet are entered in each line of the first column. Commands are placed in the cells at the intersection of other columns and rows. If at the intersection of any row and any column we get an empty cell, this means that in this internal state this symbol cannot be found.

For example, we are creating an algorithm for finding the difference between two positive integers (in the decimal number system), if it is known that the first number is greater than the second, and there is a minus sign between them.

The program field will look like this:

The command format in each cell is aKq. Here:
a is the new content of the current cell (a new symbol of the external alphabet that is entered into the current cell), K is the command of the Turing machine’s tape mechanism (left, right, stop), q is the new internal state of the Turing machine.

The button will launch the program. If execution has not been suspended, it always starts from the zero internal state Q0.

The program can be completed step by step. To do this, click on the button on the toolbar (if the buttons are not visible, you need to select the menu item View | Toolbar) or select from the main menu Start | Step by step. If you need to completely interrupt the execution of the program, this can be done using the button on the toolbar or using the main menu ( Start | Abort). Menu item Speed allows you to adjust the speed of program execution.

The program will continue to execute until the “Stop” command is encountered or some error occurs.

If you have any questions while working with the interpreter program, please refer to the help file Algo2000.hlp. It, as well as the “Algo2000” program itself, can be found on the website of the newspaper “Informatics” http://inf.1september.ru in the “Download” section.

Artificial intelligence (AI, English: Artificial intelligence, AI) - the science and technology of creating intelligent machines, especially intelligent computer programs. AI is related to the similar task of using computers to understand human intelligence, but is not necessarily limited to biologically plausible methods.

What is artificial intelligence

Intelligence(from Lat. intellectus - sensation, perception, understanding, understanding, concept, reason), or mind - a quality of the psyche consisting of the ability to adapt to new situations, the ability to learn and remember based on experience, understand and apply abstract concepts and use one’s knowledge for environmental management. Intelligence is the general ability to cognition and solve difficulties, which unites all human cognitive abilities: sensation, perception, memory, representation, thinking, imagination.

In the early 1980s. Computational scientists Barr and Fajgenbaum proposed the following definition of artificial intelligence (AI):

Later, a number of algorithms and software systems began to be classified as AI, the distinctive property of which is that they can solve some problems in the same way as a person thinking about their solution would do.

The main properties of AI are understanding language, learning and the ability to think and, importantly, act.

AI is a complex of related technologies and processes that are developing qualitatively and rapidly, for example:

• natural language text processing
• expert systems
• virtual agents (chatbots and virtual assistants)
• recommendation systems.

National strategy for the development of artificial intelligence

• Main article: National strategy for the development of artificial intelligence

AI Research

• Main article: Artificial Intelligence Research

Standardization in AI

2019: ISO/IEC experts supported the proposal to develop a standard in Russian

On April 16, 2019 it became known that the ISO/IEC subcommittee on standardization in the field of artificial intelligence supported the proposal of the Technical Committee “Cyber-physical systems”, created on the basis of RVC, to develop the “Artificial intelligence” standard. Concepts and terminology" in Russian in addition to the basic English version.

Terminological standard “Artificial intelligence. Concepts and terminology" is fundamental to the entire family of international regulatory and technical documents in the field of artificial intelligence. In addition to terms and definitions, this document contains conceptual approaches and principles for constructing systems with elements, a description of the relationship between AI and other end-to-end technologies, as well as basic principles and framework approaches to the regulatory and technical regulation of artificial intelligence.

Following the meeting of the relevant ISO/IEC subcommittee in Dublin, ISO/IEC experts supported the proposal of the delegation from Russia to simultaneously develop a terminological standard in the field of AI not only in English, but also in Russian. The document is expected to be approved in early 2021.

During the meeting, ISO/IEC experts also supported the development of a draft international document Information Technology - Artificial Intelligence (AI) - Overview of Computational Approaches for AI Systems, in which Russia acts as a co-editor. The document provides an overview of the current state of artificial intelligence systems, describing the main characteristics of the systems, algorithms and approaches, as well as examples of specialized applications in the field of AI. The development of this draft document will be carried out by a specially created working group 5 “Computational approaches and computational characteristics of AI systems” within the subcommittee (SC 42 Working Group 5 “Computational approaches and computational characteristics of AI systems”).

Artificial intelligence technologies are in wide demand in a variety of sectors of the digital economy. Among the main factors hindering their full-scale practical use is the underdevelopment of the regulatory framework. At the same time, it is the well-developed regulatory and technical framework that ensures the specified quality of technology application and the corresponding economic effect.

In the area of ​​artificial intelligence, TC Cyber-Physical Systems, based on RVC, is developing a number of national standards, the approval of which is planned for the end of 2019 - beginning of 2020. In addition, work is underway together with market players to formulate a National Standardization Plan (NSP) for 2020 and beyond. TC "Cyber-physical systems" is open to proposals for the development of documents from interested organizations.

2018: Development of standards in the field of quantum communications, AI and smart city

On December 6, 2018, the Technical Committee “Cyber-Physical Systems” based on RVC together with the Regional Engineering Center “SafeNet” began developing a set of standards for the markets of the National Technology Initiative (NTI) and the digital economy. By March 2019, it is planned to develop technical standardization documents in the field of quantum communications, and, RVC reported. Read more.

Impact of artificial intelligence

Risk to the development of human civilization

Impact on the economy and business

• The impact of artificial intelligence technologies on the economy and business

Impact on the labor market

Artificial Intelligence Bias

At the heart of everything that is the practice of AI (machine translation, speech recognition, natural language processing, computer vision, automated driving and much more) is deep learning. It is a subset of machine learning, characterized by the use of neural network models, which can be said to mimic the workings of the brain, so it would be a stretch to classify them as AI. Any neural network model is trained on large data sets, so it acquires some “skills,” but how it uses them remains unclear to its creators, which ultimately becomes one of the most important problems for many deep learning applications. The reason is that such a model works with images formally, without any understanding of what it does. Is such a system AI and can systems built on machine learning be trusted? The implications of the answer to the last question extend beyond the scientific laboratory. Therefore, media attention to the phenomenon called AI bias has noticeably intensified. It can be translated as “AI bias” or “AI bias”. Read more.

Artificial Intelligence Technology Market

AI market in Russia

Global AI market

Areas of application of AI

The areas of application of AI are quite wide and cover both familiar technologies and emerging new areas that are far from mass application, in other words, this is the entire range of solutions, from vacuum cleaners to space stations. You can divide all their diversity according to the criterion of key points of development.

AI is not a monolithic subject area. Moreover, some technological areas of AI appear as new sub-sectors of the economy and separate entities, while simultaneously serving most areas in the economy.

The development of the use of AI leads to the adaptation of technologies in classical sectors of the economy along the entire value chain and transforms them, leading to the algorithmization of almost all functionality, from logistics to company management.

Using AI for Defense and Military Affairs

Use in education

Using AI in business

AI in the fight against fraud

On July 11, 2019 it became known that in just two years artificial intelligence and machine learning will be used to combat fraud three times more often than in July 2019. Such data was obtained during a joint study by SAS and the Association of Certified Fraud Examiners (ACFE). As of July 2019, such anti-fraud tools are already used in 13% of organizations that took part in the survey, and another 25% said that they plan to implement them within the next year or two. Read more.

AI in the electric power industry

• At the design level: improved forecasting of generation and demand for energy resources, assessment of the reliability of power generating equipment, automation of increased generation when demand surges.
• At the production level: optimization of preventive maintenance of equipment, increasing generation efficiency, reducing losses, preventing theft of energy resources.
• At the promotion level: optimization of pricing depending on the time of day and dynamic billing.
• At the level of service provision: automatic selection of the most profitable supplier, detailed consumption statistics, automated customer service, optimization of energy consumption taking into account the customer’s habits and behavior.

AI in manufacturing

• At the design level: increasing the efficiency of new product development, automated supplier assessment and analysis of spare parts requirements.
• At the production level: improving the process of completing tasks, automating assembly lines, reducing the number of errors, reducing delivery times for raw materials.
• At the promotion level: forecasting the volume of support and maintenance services, pricing management.
• At the level of service provision: improving planning of vehicle fleet routes, demand for fleet resources, improving the quality of training of service engineers.

AI in banks

• Pattern recognition - used incl. to recognize customers in branches and convey specialized offers to them.

AI in transport

• The auto industry is on the verge of a revolution: 5 challenges of the era of unmanned driving

AI in logistics

AI in brewing

AI in the judiciary

Developments in the field of artificial intelligence will help radically change the judicial system, making it fairer and free from corruption schemes. This opinion was expressed in the summer of 2017 by Vladimir Krylov, Doctor of Technical Sciences, technical consultant at Artezio.

The scientist believes that existing solutions in the field of AI can be successfully applied in various spheres of the economy and public life. The expert points out that AI is successfully used in medicine, but in the future it can completely change the judicial system.

“Looking at news reports every day about developments in the field of AI, you are only amazed at the inexhaustible imagination and fruitfulness of researchers and developers in this field. Reports on scientific research are constantly interspersed with publications about new products bursting onto the market and reports of amazing results obtained through the use of AI in various fields. If we talk about expected events, accompanied by noticeable hype in the media, in which AI will again become the hero of the news, then I probably won’t risk making technological forecasts. I can assume that the next event will be the appearance somewhere of an extremely competent court in the form of artificial intelligence, fair and incorruptible. This will happen, apparently, in 2020-2025. And the processes that will take place in this court will lead to unexpected reflections and the desire of many people to transfer to AI most of the processes of managing human society.”

The scientist recognizes the use of artificial intelligence in the judicial system as a “logical step” to develop legislative equality and justice. Machine intelligence is not subject to corruption and emotions, can strictly adhere to the legislative framework and make decisions taking into account many factors, including data that characterize the parties to the dispute. By analogy with the medical field, robot judges can operate with big data from government service repositories. It can be assumed, that

Music

Painting

In 2015, the Google team tested neural networks to see if they could create images on their own. Then artificial intelligence was trained using a large number of different pictures. However, when the machine was “asked” to depict something on its own, it turned out that it interpreted the world around us in a somewhat strange way. For example, for the task of drawing dumbbells, the developers received an image in which the metal was connected by human hands. This probably happened due to the fact that during the training stage, the analyzed pictures with dumbbells contained hands, and the neural network interpreted this incorrectly.

On February 26, 2016, at a special auction in San Francisco, Google representatives raised about $98 thousand from psychedelic paintings created by artificial intelligence. These funds were donated to charity. One of the most successful pictures of the car is presented below.

A painting painted by Google's artificial intelligence.

We see it all the time. “RESTful” this, “REST” protocol that, etc. However, a lot of us don’t really understand exactly what it means. We’ll fix exactly that gap in this article!

State

In computer science (and mathematics, to some extent), there is a concept of state. A certain system can be in state A or it can be in state B or it can be a bunch of other states (usually, a finite list of states).

As an example, let us say that you write a program which turns the screen red if the temperature is more than 80 degrees farenheit or turns it blue if the temperature is less than 80 degrees farenheit.

We can call the first state (temp > 80 degrees) state “A” and the second state (temp< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

That is the general idea of ​​state. Here’s the definition given by the all-knowing Wikipedia:

“In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given point in time, which is used by the circuit or program.”

In short, it is a sort of “combination” of all the information that the program takes into account.

Now, we’re going to make a leap into something that’s considered largely theoretical and useless and then somehow connect to the very practical world of REST.

Turing machines

There was this man named Alan Turing, and he was quite a smart mathematician with an interest in the workings of computers. He conceived an imaginary computer (which, as we will see, is actually impossible to actually build) which he used to reason about things that happen in real computers.

The computer consists of a tape of infinite length, with a head through which the tape passes. The tape has “cells”, to which information can be written (numbers, colors, etc.) The tape moves through this machine, left or right, one cell at a time. The machine scans in whatever is already on the tape and, depending on what state it is in, it writes something back onto the tape then, subsequently, changes its state.

You may want to read that definition again for it to sink in completely. The essence of the idea is that it makes operations on memory based on state and states changes according to operations on memory.

This seems like a fairly useless theoretical fantasy (although, there is absolutely nothing wrong with that, read A Mathematician’s Apology if you’re wondering why people care to take an interest in theoretical stuff). However, it is quite possibly the most fundamental concept of computer science.

Using the Turing Machine, computer scientists are able to reason about any algorithm that can be run on a computer. In fact, the Turing machine has led to many advances in computer science.

So, the Turing Machine shows us that today (note: I’m not considering graph reduction processors), literally everything in computer science is based off the idea of ​​state.

The Network

Then came along the concept of the internet. This is a place where packets can go haywire and are resent until they reach their destination. In general, there is never a complete transmission of full data.

Clients come in quickly and leave twice as fast. As such, holding onto client state doesn’t make much sense when working on a network system.

Also, in general, holding too much state in a system has been a cause for major pain (which also leads to funcitonal programming languages, which do not allow for the holding of state in a large portion of your code).

Now, people needed a network protocol for the internet which was simple, fast and handled management of state well in an extremely dynamic environment.

That protocol was HTTP, and the theory that grew out of the work on HTTP was labeled REST.

REST

REST stands for: REpresentational State Transfer. It is a system built around the “client-server” concept that networks are built on top of (well, ther are also peer to peer type networks, but, client-sever is arguably the simplest and most tested architecture). The name itself is slightly misleading, since the server is completely state-free!

There are a few constraints that all systems that claim to be “RESTful” must follow.

First of all, it must be a client-server system. This constraint has been modified in the past, but in the formal definition (and, for the theory of REST to work properly), we have servers to which clients can connect.

The server is fully stateless. This means that for each client request to the server, no state is reserved on the server. For example, if a client (using HTTP), requests the index page and subsequently requests the /user/home page, the two requests are completely independent of each other. The client holds all of the state of the system (hence, we have the back button).

Responses from the server must be cacheable, which means that there must be a system on the server which identifies responses as cacheable or not, so that clients (e.g. web browsers) can take advantage of the cache.

Finally, we must have a simple, clean, and uniform interface. If you have had some experience with how HTTP works, the request forms are very simple. They are largely verbs and nouns with a very easy to parse and human-readable format. SOAP is another form of a network protocol which absolutely obliterates this requirement and, therefore, is often very difficult to work with.

Now, what do all of these properties, when taking together, entail?

Implications of REST

They let us build systems that are cleanly seperated, scalable, and debugged easily.

Let us consider the restriction of statelessness on the server first, it may well be the most important (and, also, the most often violated by so-called RESTful architectures) bit.

As previously mentioned, in a client-server architecture the clients are very nimble; they fire requests and suddenly kill all communication. In this kind of a situation, it is much cleaner to not save state about the client on the server. This lets us reason about HTTP servers very easily; each client request may be treated as if it is a completely new client, and it wouldn’t make a penny of a difference.

Secondly, cacheable responses mean that the clients are able to get data much faster, because often times, the data can be retrieved from the client’s memory. This immediately increases client performance and, in some systems, server scalability.

The uniform interface may just be the most important. Having worked with SOAP, I can tell you that HTTP’s simple format is a blessing when trying to debug server code and the same applies to other RESTful systems.

Designing a RESTful System

Let’s say we need to write a server that returns stock quotes, as well as retaining a list of stock quotes to monitor (and, the user can either add to or clear the list).

This is an excellent case for a RESTful system, because it is inherently independent of identity of client. Therefore, the server needs not hold any state about the client.

We first start by defining how the protocol language will work (a bit like the GET and POST verbs of HTTP):

GETQUOTE ticker- gives the price for a particular stock
ADDTICKER ticker- adds the given stock to the list
GETLIST - gets a comma seperated list of stocks in the list

That’s a fairly simple protocol, and, doesn’t hold any state on the server. Now, as for caching, we may say that we update the prices every hour, so caches more than one hour old may be thrown away.

And, that’s all there is to it! Of course, we still have to implement this, but, the general idea of ​​the system is quite simple and clean!

Conclusion

Hopefully, this article gave you a solid understanding of REST.

Also, I hope that you will now be able to call out people who throw around the term “RESTful” too much - I can tell you, there’s a lot of them!

TURING

TURING(Turing) Alan (1912-54), English mathematician and logician who formulated theories that later became the basis of computer technology. In 1937 he came up with Turing machine - a hypothetical machine capable of transforming a set of input commands. It was the forerunner of modern computers. Turing also used the idea of ​​a computer to give an alternative and simpler proof of Gödel's incompleteness theorem. Turing played a major role in solving Enigma, a complex encryption method used by Germany during World War II. In 1948 he participated in the creation of one of the world's first computers. In 1950 he came up with Turing test - it was supposed to be a test of a computer's ability to “think.” Essentially, it stated that a person would not be able to distinguish a dialogue with a machine from a dialogue with another person. This work paved the way for the creation of ARTIFICIAL INTELLIGENCE. Turing was also involved in theoretical biology. In progress "Chemical basis of morphogenesis"(1952) he proposed a model describing the origin of the various structural patterns of organisms in biology. Since then, such models have often been used to describe and explain many systems observed in nature. Turing committed suicide after being officially accused of homosexuality.

Scientific and technical encyclopedic dictionary.

See what "TURING" is in other dictionaries:

Turing, Alan Mathison Alan Turing Alan Mathison Turing Monument in Sackville Park Date of birth ... Wikipedia

- (Turing) Alan Mathieson (1912 54), English mathematician. In 1936-1937 he introduced the mathematical concept of an abstract equivalent of an algorithm, or a computable function, which was then called the Turing machine... Modern encyclopedia

- (Turing), Alan Mathieson (June 23, 1912 - June 7, 1954) - English. logician and mathematician. In 1936–37 he proposed an idealized machine model of computation. process - a computational scheme close to the actions of the person performing the calculations, and put forward... ... Philosophical Encyclopedia

Turing A.- Turing A. English mathematician. Topics information security EN Turing… Technical Translator's Guide

Alan Turing Alan Turing Monument in Sackville Park Date of birth: June 23, 1912 Place of birth: London, England Date of death: June 7, 1954 ... Wikipedia

Turing- English mathematician Alan M. Turing, one of the creators of the logical foundations of computer technology, in particular, gave one of the formal definitions of the algorithm; proved that there is a class of computers that can simulate... ... Lem's World - Dictionary and Guide

- (Turing) Alan Mathieson (23.6.1912, London, 7.6.1954, Wilmslow, near Manchester), English mathematician. Fellow of the Royal Society (1951). After graduating from Cambridge University (1935), he worked on his doctoral dissertation at Princeton... ... Great Soviet Encyclopedia

Turing A. M.- TURING (Turing) Alan Mathieson (191254), English. mathematician. Basic tr. in mathematics logic, calculates. mathematics. In 193637 he introduced mathematics. the concept of an abstract equivalent of an algorithm, or a computable function, then called. car T... Biographical Dictionary

- (full Alan Mathison Turing) (June 23, 1912, London June 7, 1954, Wilmslow, UK), British mathematician, author of works on mathematical logic and computational mathematics. In 1936-1937 he introduced the mathematical concept... encyclopedic Dictionary

Books

• Can a machine think? General and logical theory of automata. Issue 14, Turing A., This book, containing the works of Alan Turing and John von Neumann, who were at the origins of the creation of the first thinking computers, belongs to the classics of philosophical-cybernetic... Category: Databases Series: Artificial Sciences Publisher: URSS, Manufacturer: URSS,
• Can a machine think? General and logical theory of automata. Issue No. 14, Turing A., This book, containing the works of Alan Turing and John von Neumann, who were at the origins of the creation of the first “thinking machines” of computers, belongs to the classics of the philosophical-cybernetic direction... Category: