Until now, it has been convenient for us to refer to programmer experience when talking about algorithms, programs, interpreters, step-by-step execution, etc. This allowed us to ignore the details of the construction of certain algorithms under the pretext that the reader would easily restore them (or at least believe that not every reader in his life wrote a Pascal interpreter in Pascal).

But in some cases this is not enough. Let, for example, we want to prove the algorithmic undecidability of some problem, the definition of which does not say anything about programs (in this section, for example, we will prove the undecidability of the problem of equality of words in semigroups defined by generators and relations). It's usually done like this. We show that the stopping problem reduces to this problem. To do this, we model the operation of an arbitrary algorithm in terms of the problem under consideration (what this means will be clear from the example below). At the same time, it is important for us that the definition of the algorithm is as simple as possible.

So our plan is this. We will describe a fairly simply definable class of machines (it can be chosen in different ways; we will use so-called Turing machines), then declare that every computable function can be computed on such a machine, and then show that the question of stopping a Turing machine can be reduced to to the question of the equality of words in a semigroup.

Another reason why simple computational models are important (there are many different types of Turing machines, address machines, etc.) is related to the theory of computational complexity, when we begin to be interested in lead time programs. But this question goes beyond the classical theory of algorithms.

Turing machines: definition

Turing machine has infinity in both directions tape, divided into squares ( cells). Each cell can contain some symbol from a fixed (for a given machine) finite set called alphabet of this machine. One of the characters of the alphabet is highlighted and is called a “space”; it is assumed that initially the entire tape is empty, that is, filled with spaces.

A Turing machine can change the contents of a tape using a special reader and writer. heads, which moves along the tape. At each moment the head is in one of the cells. The Turing machine receives information from the head about what symbol it sees, and depending on this (and on its internal state) decides what to do, that is, which symbol to write in the current cell and where to move after that (left, right, or stay on site). At the same time, the internal state of the machine also changes (we assume that the machine, not counting the tape, has a finite memory, that is, a finite number of internal states). We also need to agree where we start and when we finish the work.

Thus, to define a Turing machine, you need to specify the following objects:

The transition table is arranged as follows: for each pair a triple is indicated. Here the shift is one of the numbers -1 (to the left), 0 (in place) and 1 (to the right). Thus, the transition table is a function of the type S x A -> S x A x (-1,0,1) defined on those pairs in which the state is not final.

It remains to describe the behavior of the Turing machine. At every moment there is some configuration, consisting of the contents of the tape (formally speaking, the contents of the tape is an arbitrary mapping Z -> A), the current position of the head (some integer) and the current state of the machine (element S). The transformation of the configuration into the next one occurs according to natural rules: we look in the table what needs to be done for a given state and for a given symbol, that is, we find out the new state of the machine, change the symbol to the specified one and then move the head to the left, right or leave it in place. Moreover, if the new state is one of the final ones, the machine’s operation ends. It remains to agree on how we provide information to the input of the machine and what is considered the result of its work. We will assume that the machine's alphabet, in addition to the space, contains the characters 0 and 1 (and possibly some other characters). The input and output of the machine will be finite sequences of zeros and ones (binary words). The input word is written on an empty tape, the head of the machine is placed in its first cell, the machine is brought to its initial state and started. If the machine stops, the result is a binary word, which can be read starting at the head position and moving to the right (until a character other than 0 and 1 appears).

Thus, any Turing machine defines some partial function on binary words. It is natural to call all such functions computable on Turing machines.

Turing machines: discussion

Of course, our definition contains many specific details that could be changed. For example, a tape can only be endless in one direction. You can give the car two ribbons. We can consider that the machine can either write a new character or move, but not both. You can limit the alphabet, considering, say, that it must have exactly 10 characters. You can demand that at the end there is nothing on the tape except the result of the work (the remaining cells must be empty). All of the above and many other changes do not change the class of functions computable on Turing machines. Of course, there are also some harmless changes. For example, if you forbid a car to move to the left, then this will radically change things; essentially, the tape will become useless, since it will no longer be possible to return to the old recordings.

How do you know which changes are harmless and which are not? Apparently, some experience in practical programming on Turing machines is needed here, at least a little. After this, you can already imagine the capabilities of the machine without writing out the entire program, but guided only by an approximate description. As an example, we will describe a machine that doubles the input word (produces the word XX if the input was the word X).

If the machine sees a space (the input word is empty), it stops working. If not, it remembers the current character and puts a mark (in the alphabet, in addition to the characters 0 and 1, there will also be their “marked variants” and ). She then moves to the right to an empty cell, after which she writes a copy of the memorized symbol there. She then moves left until marked; Having buried himself in the mark, he moves back and remembers the next character, and so on, until he has copied the entire word.

Having some experience, you can see behind all these phrases specific pieces of the program for the Turing machine. For example, the words “remembers the symbol and moves to the right” mean that there are two groups of states, one for the situation when a zero is remembered, the other when a one is remembered, and within each group the movement to the right is programmed to the first empty cell.

With a little more experience, you can understand that there is an error in this description; there is no mechanism for stopping when the entire word is copied, since the copies of the characters are no different from the characters of the original word. It is also clear how to correct the error: you need to write special characters and as copies, and at the last stage, delete all marks.

77 . Show that the reversal function, which turns a word backwards, is Turing machine computable.

Another example of informal reasoning: let's explain why it is possible not to use additional characters other than 0, 1 and the empty character. Let there be a machine with a large alphabet of N characters. Let's build a new machine that will simulate the operation of the old one, but each cell of the old one will correspond to a block of k cells of the new one. The block size (the number k) will be fixed so that within the block all the characters of a large alphabet can be encoded with zeros and ones. The original characters 0 , 1 , and blank will be encoded as 0 followed by (k-1) blank characters, 1 followed by (k-1) blank characters, and a group of k blank characters. First, you need to move the letters of the input word apart by a distance k, which can be done without additional symbols (when you reach the outer letter, move it away, then when you reach the next one, move it and the outermost one, and so on); you just need to understand that you can identify the end of a word as a position followed by more than k empty characters. Clearly, in this process we must store some finite amount of information in memory, so this is possible. After this, it is already possible to simulate the operation of the original machine step by step, and for this, a finite memory (e a finite number of states) is also sufficient, since only a small neighborhood of the head of the simulated machine is important to us. Finally, we need to compress the result back.

To conclude the discussion, we present the argument promised above in favor of the fact that any computable function is computable on a Turing machine. Let there be a function that a person can calculate. At the same time, he must naturally use a pencil and paper, since amount of information the amount he can store “in his mind” is limited. We will assume that he writes on separate sheets of paper. In addition to the current sheet, there is a stack of papers on the right and a stack on the left; You can put the current sheet into any of them, having completed work with it, and take the next one from the other pile. A man has a pencil and an eraser. Since very small letters are not visible, the number of clearly distinguishable states of the sheet is finite, and we can assume that at each moment one letter from some finite (albeit very large) alphabet is written on the sheet. A person also has a finite memory, so his state is an element of some finite set. In this case, you can draw up some table in which it is written down how his work on a sheet with a given content, started in a given state, will end (what will be on the sheet, what state the person will be in and from which pack the next sheet will be taken). It is now clear that human actions exactly correspond to the operation of a Turing machine with a large (but finite) alphabet and a large (but finite) number of internal states.

Introduction

In 1936, Alan Turing proposed an abstract universal executor to clarify the concept of an algorithm. Its abstractness lies in the fact that it represents a logical computational construct, and not a real computing machine. The term "universal performer" means that a given performer can imitate any other performer. For example, operations that are performed by real computers can be simulated on a universal executor. Subsequently, the computational design invented by Turing was called a Turing machine.

The purpose of this course work is to create a program that implements a Turing machine in the functional programming language Haskell. As an example, we will implement a Turing machine designed to multiply a decimal number by 2.

To achieve this goal, it is necessary to solve the following tasks: study the principles of operation of the Turing machine, its structure, consider algorithmically unsolvable problems, choose a data structure, describe the functions being implemented, and also give examples of the program.

Basic provisions of the Turing machine

The Turing machine got its name from the English mathematician Alan Turing, who in 1937 proposed a method for formally specifying algorithms using some abstract machine. The essence of the work comes down to the following. There is a potentially infinite tape, divided into cells, each of which can contain one character from some finite alphabet. A Turing machine has a read/write head that allows you to read a character in the current cell, write a character to a cell, and move the head left or right to an adjacent cell. The machine operates discretely, in cycles, and at each cycle it is in one of the possible states, of which there is a finite number. For each pair (state, symbol being observed), a triple is defined (character being written, head movement, new state). Before operation begins, the Turing machine is in the initial state, and the read-write head scans the leftmost non-empty cell on the tape. Thus, while reviewing the next symbol, the machine writes a new symbol (perhaps the same one), moves the head to the left, to the right, or remains in place and goes into a new state or remains in the same state.

A Turing machine consists of three parts: a tape, a read (write) head and a logic device, as is clearly shown in Figure 1.

The tape acts as external memory. It is considered unlimited (infinite). This alone indicates that the Turing machine is a model device, since no real device can have an infinite memory.

Figure 1 - Turing machine circuit

A Turing machine operates in some arbitrary finite alphabet A = (_, a1…an) - this alphabet is called external. It contains a special character - _, called a blank sign - sending it to any cell erases the character that was previously there and leaves the cell empty. Only one character can be written to each tape cell. The information stored on the tape is represented by a finite sequence of external alphabet characters other than the empty character.

The head is always located above one of the tape cells. Work occurs in cycles (steps). The system of commands executed by the head is extremely simple: at each clock cycle it replaces the sign in the observed cell ai with the sign aj. In this case, combinations are possible:

1) аj = аi - means that the sign in the observed cell has not changed;

2) ai ? _, аj = _ - the sign stored in the cell is replaced with an empty one, i.e. erased;

3) аi = _, аj ? _ - an empty character is replaced by a non-empty one (with number j in the alphabet), i.e. a sign is inserted;

4) ai ? аj ? _ - corresponds to replacing one character with another.

Thus, the Turing machine implements a system of extremely simple information processing commands. This system of processing commands is also complemented by an extremely simple system of commands for moving the tape: one cell to the left, one cell to the right and stay in place, i.e. As a result of the command execution, the address of the cell being monitored can either change to 1 or remain unchanged.

However, although the actual movement of the tape occurs, the movement of the head relative to the section being viewed is usually considered. For this reason, the command for shifting the tape to the left is designated R (Right), shifting to the right is L (Left), and no shift is designated S (Stop). We will talk specifically about shifting the head and consider R, L and S to be commands for its movement.

The elementary nature of these commands means that if it is necessary to access the contents of a certain cell, it is found only through a chain of individual shifts by one cell. Of course, this significantly lengthens the processing process, but it allows you to do without numbering cells and using commands to go to the address, i.e. reduces the number of truly elementary steps, which is important from a theoretical point of view.

Processing information and issuing commands to write a sign, as well as shift the tape in a Turing machine, is carried out by a logical device (LU). The LU can be in one of the states that form a finite set and are denoted by Q =(q1...qm, q0), and the state q0 corresponds to the completion of work, and q1 is the initial (initial) state. Q together with the signs R, L, S form the internal alphabet of the machine. The LU has two input channels (ai, qi) and three output channels (ai+1, qi+1, Di+1). The LU diagram of a Turing machine is shown in Figure 2.

Figure 2 - LU diagram of a Turing machine

It is necessary to understand the circuit as follows: at cycle i, a sign from the currently viewed cell (ai) is supplied to one input of the LU, and a sign indicating the state of the LU at the moment (qi) is supplied to the other input. Depending on the received combination of signs (ai, qi) and the existing processing rules, the LU generates and sends a new sign (ai+1) to the observed cell via the first output channel, issues a command to move the head (Di+1 from R, L and S), and also gives a command to transition to the next state (qi+1). Thus, the elementary step (cycle) of the operation of a Turing machine is as follows: the head reads a symbol from the cell being monitored and, depending on its state and the read symbol, executes a command that specifies which symbol to write (or erase) and what movement to make . At the same time, the head goes into a new state. The operation diagram of such a machine is shown in Figure 3.

Figure 3 - Diagram of the functioning of a Turing machine

This diagram reflects the division of memory into external and internal. The external one is presented, as indicated, in the form of an endless tape - it is designed to store information encoded in the symbols of the external alphabet. The internal memory is represented by two cells for storing the next command during the current clock cycle: the next state (qi+1) is transferred to Q from the LU and stored, and the shift command (Di+1) is stored in D. From Q, via the feedback line, qi+1 enters the LU, and from D, the command is sent to the actuator, which, if necessary, moves the tape one position to the right or left.

The general rule by which a Turing machine works can be represented by the following notation: qi aj > qi" aj" Dk, i.e. after viewing the symbol aj by the head in the qi state, the symbol aj is written into the cell, the head goes into the qi state, and the tape makes a movement Dk. For each combination qi aj there is exactly one transformation rule (there are no rules only for q0, since the machine stops once it gets into this state). This means that the logical block implements a function that associates each pair of input signals qi aj with one and only one triple of output signals qi "aj" Dk - it is called the logical function of the machine and is usually represented in the form of a table (functional diagram of the machine), the columns of which are indicated by state symbols , and the lines are signs of the external alphabet. If there are n signs of the external alphabet, and the number of LU states is m, then, obviously, the total number of transformation rules will be n×m.

A specific Turing machine is specified by enumerating the elements of the sets A and Q, as well as the logical function that the LU implements, i.e. a set of transformation rules. It is clear that there can be infinitely many different sets A, Q and logical functions, i.e. and there are also infinitely many Turing machines.

It is also necessary to introduce the concept of machine configuration, i.e. sets of states of all tape cells, LU states and head position. It is clear that the machine configuration can contain any number of characters from the external alphabet and only one character from the internal one.

Before starting work, an initial word a of finite length in the alphabet A is written onto an empty tape; the head is installed above the first character of the word a, the LU is transferred to state q1 (i.e., the initial configuration looks like q1a). Since only one transformation rule is implemented in each configuration, the initial configuration uniquely determines all subsequent operation of the machine, i.e. the entire sequence of configurations until the termination of operation.

Depending on the initial configuration, two scenarios are possible:

1) after a finite number of cycles, the machine stops at the stop command; in this case, the final configuration corresponding to the output information appears on the tape;

2) there is no stopping.

In the first case, they say that this machine is applicable to the initial information, in the second - not. The entire set of input configurations under which the machine provides a result forms a class of problems to be solved. Obviously, it makes no sense to use a Turing machine for a problem that is not included in the class of solvable ones.

There is a Turing hypothesis: if a procedure is well defined and mechanical in nature, then one can reasonably assume that there will be a Turing machine capable of performing it. It cannot be proven because it connects the loose definition of the concept of an algorithm with the strict definition of a Turing machine. This conjecture can be refuted if one can give an example of an algorithm that cannot be implemented using a Turing function circuit. However, all algorithms known so far can be specified using Turing functional circuits.

simulator for learning the universal performer

What it is?

The Turing Machine simulator is a training model of a universal executor (abstract computing machine), proposed in 1936 by A. Turing to clarify the concept of an algorithm. According to Turing's thesis, any algorithm can be written as a program for a Turing machine. It has been proven that the Turing machine is equivalent in its capabilities to the Post machine and normal Markov algorithms.

A Turing machine consists of a carriage (reading and writing head) and an endless tape divided into cells. Each cell of the tape can contain a character from some alphabet A=(a 0 ,a 1 ,…,a N ) . Any alphabet contains a space character, which is denoted as a 0 or Λ. When entering commands, the space is replaced with an underscore "_".

A Turing machine is an automaton that is controlled by a table. The rows in the table correspond to the characters of the selected alphabet A, and the columns correspond to the states of the machine Q=(q 0 ,q 1 ,…,q M ) . At the beginning of its operation, the Turing machine is in state q 1 . State q 0 is the final state: once in it, the machine ends its operation.

In each cell of the table, corresponding to some symbol a i and some state q j, there is a command consisting of three parts:

1. character from the alphabet A;
2. direction of movement: > (right),
3. new state of the machine

News

1. Falina I.N. The topic “Turing Machine” in the school computer science course (inf.1september.ru).
2. Mayer R.V. Post and Turing machines (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Turing machine and Markov algorithms. Problem solving, M.: MSU, 2006.
4. Bekman I.N. Computer science. Lecture 7. Algorithms (profbeckman.narod.ru)
5. Soloviev A. Discrete mathematics without formulas (lib.rus.ec)
6. Ershov S.S. Elements of the theory of algorithms, Chelyabinsk, SUSU Publishing Center, 2009.
7. Varpakhovsky F.L. Elements of the theory of algorithms, M: Prosveshchenie, 1970.
8. Vereshchagin N.K., Shen A. Computable functions, M: MTsNMO, 1999.

What to do about it?

At the top of the program there is an editor field in which you can enter the problem condition in free form.

The ribbon moves left and right using the buttons located to the left and right of it. By double-clicking a ribbon cell (or right-clicking) you can change its contents.

Using the menu Ribbon you can store the state of the tape in the internal buffer and restore the tape from the buffer.

In field Alphabet The characters of the selected alphabet are specified. A space is automatically added to entered characters.

The program is typed in the table at the bottom of the window. The first column contains alphabetic characters and is filled in automatically. The first line lists all possible states. You can add and remove table (state) columns using the buttons located above the table.

When entering a command into a table cell, you first need to enter a new character, then the direction of the transition and the state number. If a character is omitted, it is left unchanged by default. If the state number is omitted, by default the state of the machine does not change.

Right in the field A comment You can enter free-form comments on the solution. Most often it explains what each state of a Turing machine means.

The program can be executed continuously (F9) or in steps (F8). The command that will now be executed is highlighted with a green background. Execution speed is adjustable using the menu Speed.

Turing machine problems can be saved in files. The task condition, alphabet, program, comments and the initial state of the tape are saved. When a task is loaded from a file and saved to the file, the tape state is automatically buffered.

If you notice an error or have suggestions, comments, complaints, requests or statements, write.

Technical requirements

The program runs under the operating systems of the line Windows on any modern computer.

License

The program is free for non-commercial use. The source code of the program is not distributed.

The program comes " as is", that is, the author does not bear any responsibility for all possible consequences of its use, including moral and material losses, equipment failure, physical and mental injuries.

When posting the program on other websites, a link to the original source is required.

1. 1) publication of materials in any form, including posting of materials on other Web sites;
2. 2) distribution of incomplete or altered materials;
3. 3) inclusion of materials in collections on any media;
4. 4) obtaining commercial benefits from the sale or other use of materials.

Downloading materials means you accept the terms of this license agreement.

Download

After unpacking the archive, the program is in working order and does not require any additional installations.

1. Description of the Turing machine. 3

1.1 Properties of the Turing machine as an algorithm. 5

2. Complexity of algorithms. 7

2.1 Complexity of problems... 9

3. Turing machine and algorithmically unsolvable problems.. 12

Conclusion. 16

References.. 18

Introduction

A Turing machine is a very simple computing device. It consists of a tape of infinite length, divided into cells, and a head that moves along the tape and is capable of reading and writing characters. Also, a Turing machine has such a characteristic as a state, which can be expressed as an integer from zero to some maximum value. Depending on the state, a Turing machine can perform one of three actions: write a symbol into a cell, move one cell to the right or left, and set the internal state.

The design of a Turing machine is extremely simple, but it can run almost any program. To perform all these actions, a special table of rules is provided, which specifies what needs to be done for various combinations of current states and symbols read from the tape.

In 1947, Alan Turing expanded the definition to describe a "universal Turing machine." Later, to solve certain classes of problems, a variation of it was introduced, which made it possible to perform not one task, but several.

1. Description of the Turing machine

The background to the creation of this work is connected with the formulation of unsolved mathematical problems by David Hilbert at the International Mathematical Congress in Paris in 1900. One of them was the task of proving the consistency of the axiom system of ordinary arithmetic, which Hilbert later clarified as the “decidability problem” - finding a general method for determining the satisfiability of a given statement in the language of formal logic.

Turing's paper precisely gave the answer to this problem - Hilbert's second problem turned out to be unsolvable. But the significance of Turing's paper went far beyond the problem for which it was written.

Here is a description of this work, belonging to John Hopcroft: “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, without creative intervention ", he showed how this idea could be embodied in the form of a detailed model of the computational process. The resulting model of computation, in which each algorithm was broken down into a sequence of simple, elementary steps, was the logical construct that was later called the Turing machine."

A Turing machine is an extension of the finite state machine model, an extension that includes a potentially infinite memory with the ability to move (move) from the currently viewed cell to its left or right neighbor.

Formally, a Turing machine can be described as follows. Let the following be given:

a finite set of states – Q, in which a Turing machine can be;

finite set of tape symbols – Г;

function δ (transition function or program), which is specified by mapping a pair from the Cartesian product Q x Г (the machine is in state qi and is viewing the symbol gi) into a triple of the Cartesian product Q x Г x (L,R) (the machine goes to state qi, replaces the gi symbol with the gj symbol and moves left or right one tape symbol) – Q x Г-->Q x Г x (L,R)

one character from Г-->е (empty);

the subset Σ є Г - -> is defined as a subset of the input symbols of the tape, and е є (Г - Σ);

one of the states – q0 є Q is the initial state of the machine.

The problem to be solved is specified by recording a finite number of symbols from the set Σ є Г – Si є Σ onto tape:

eS1S2S3S4... ... ...Sne

after which the machine is transferred to the initial state and the head is installed at the leftmost non-empty symbol (q0,w) –, after which, in accordance with the specified transition function (qi,Si) - ->(qj,Sk, L or R), the machine begins to replace viewed symbols, move the head to the right or left and go to other states prescribed by the transition functions.

The machine stops if the transition function for the pair (qi,Si) is not defined.

Alan Turing proposed that any algorithm in the intuitive sense of the word can be represented by an equivalent Turing machine. This assumption is known as the Church–Turing thesis. Each computer can simulate a Turing machine (operations of rewriting cells, comparing and moving to another neighboring cell, taking into account changes in the state of the machine). Consequently, he can model algorithms in any formalism, and from this thesis it follows that all computers (regardless of power, architecture, etc.) are equivalent in terms of the fundamental ability to solve algorithmic problems.

1.1 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 move to the (k + 1)th step only after completing each step, since it is each step that determines what the (k + 1)th step will be.

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 determined; therefore, a correctly written Turing machine will go to state q0 in a finite number of steps, 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.

2. Complexity of algorithms

The complexity of the algorithm is determined by the computing power required to execute it. The computational complexity of an algorithm is often measured by two parameters: T (time complexity) and S (space complexity, or memory requirements). Both T and S are usually represented as functions of n, where n is the size of the input data. (There are other ways to measure complexity: the number of random bits, the width of the communication channel, the amount of data, etc.)

Typically, the computational complexity of an algorithm is expressed using the “Big O” notation, that is, it is described by the order of magnitude of the computational complexity. This is simply the term in the expansion of the complexity function that grows fastest as n increases, all lower order terms are ignored. For example, if the time complexity of a given algorithm is 4n2+7n+12, then the computational complexity is of the order of n2, written as O(n2).

Time complexity measured in this way is independent of implementation. You don't need to know the exact execution times of various instructions, nor the number of bits used to represent various variables, nor even the speed of the processor. One computer may be 50 percent faster than another, and a third may have a data bus twice as wide, but the complexity of the algorithm, measured by an order of magnitude, will not change. It's not cheating; when working with algorithms as complex as those described in this book, everything else can be neglected (up to a constant factor) compared to the order of magnitude complexity.

This notation allows you to see how the size of the input data affects the time and memory requirements. For example, if T = O(n), then doubling the input data will double the execution time of the algorithm. If T=O(2n), then adding one bit to the input data will double the execution time of the algorithm.

Typically, algorithms are classified according to their time or space complexity. An algorithm is called constant if its complexity does not depend on n: 0(1). An algorithm is linear if its time complexity is O(n). Algorithms can be quadratic, cubic, etc. All these algorithms are polynomial, their complexity is O(m), where m is a constant. Algorithms with polynomial time complexity are called polynomial time algorithms

Algorithms whose complexity is equal to O(tf(n)), where t is a constant greater than 1, and f(n) is some polynomial function of n, are called exponential. The subset of exponential algorithms whose complexity is O(cf(n)), where c is a constant and f(n) increases faster than a constant but slower than a linear function, is called superpolynomial.

Ideally, a cryptographer would like to claim that the best algorithm to break a designed encryption algorithm has exponential time complexity. In practice, the strongest statements that can be made given the current state of computational complexity theory are of the form “all known attack algorithms for a given cryptosystem have superpolynomial time complexity.” That is, the attack algorithms known to us have superpolynomial time complexity, but it is not yet possible to prove that an attack algorithm with polynomial time complexity cannot be discovered. The development of the theory of computational complexity may someday make it possible to create algorithms for which the existence of algorithms with a polynomial opening time can be excluded with mathematical accuracy.

The Turing machine is one of the most intriguing and exciting intellectual discoveries of the 20th century. It is a simple and useful abstract model of computing (computer and digital) that is general enough to implement any computing task. Thanks to its simple description and mathematical analysis, it forms the foundation of theoretical computer science. This research led to a greater understanding of digital computing and calculus, including the understanding that there were some computing problems that could not be solved on mainframe computers.

Alan Turing sought to describe the most primitive model of a mechanical device that would have the same basic capabilities as a computer. Turing first described the machine in 1936 in a paper "On computable numbers with an application to the solvability problem", which appeared in the Proceedings of the London Mathematical Society.

A Turing machine is a computing device consisting of a read/write head (or "scanner") with a paper tape running through it. The tape is divided into squares, each of which carries a single symbol - "0" or "1". The purpose of the mechanism is that it acts both as a means for input and output, and as a working memory for storing the results of intermediate stages of calculations. What does the device consist of? Each such machine consists of two components: Unlimited tape. It is infinite in both directions and is divided into cells. Automatic - controlled program, scanner head for reading and writing data. It can be in one of many states at any given moment.

Each machine connects two finite series of data: an alphabet of incoming symbols A = (a0, a1, ..., am) and an alphabet of states Q = (q0, q1, ..., qp). State q0 is called passive. It is believed that the device ends its work when it hits it. State q1 is called initial - the machine begins its calculations while at the start in it. The input word is located on the tape, one letter in a row in each position. On both sides of it there are only empty cells.

How the mechanism works

A Turing machine has a fundamental difference from computing devices - its storage device has an endless tape, whereas in digital devices such a device has a strip of a certain length. Each class of tasks is solved by only one built Turing machine. Problems of a different type require writing a new algorithm. The control device, being in one state, can move in any direction along the belt. It writes to and reads from cells the characters of a finite alphabet. During the move, an empty element is allocated and fills positions that do not contain input data. The Turing machine algorithm determines the transition rules for the control device. They set the following parameters to the read-write head: writing a new character to a cell, transitioning to a new state, moving left or right along the tape.

Mechanism properties

The Turing machine, like other computing systems, has inherent features, and they are similar to the properties of algorithms: Discreteness. The digital machine moves to the next step n+1 only after the previous one is completed. Each step executed assigns what n+1 will be. Clarity. The device performs only one action for one cell. It enters a character from the alphabet and makes one movement: left or right. Determinism. Each position in the mechanism corresponds to a single option for executing a given scheme, and at each stage the actions and the sequence of their execution are unambiguous. Productivity. The exact result for each stage is determined by a Turing machine. The program executes the algorithm and in a finite number of steps goes to state q0. Mass character. Each device is defined over the valid words included in the alphabet. Turing Machine Functions Solving algorithms often requires the implementation of a function. Depending on the possibility of writing a chain for calculation, a function is called algorithmically solvable or undecidable. As a set of natural or rational numbers, words in a finite alphabet N for the machine, the sequence of the set B is considered - words within the binary code alphabet B = (0.1). Also, the calculation result takes into account the “undefined” value that occurs when the algorithm freezes. To implement the function, it is important to have a formal language in the final alphabet and to solve the problem of recognizing correct descriptions.-

Device program

Programs for the Turing mechanism are formatted in tables in which the first row and column contain symbols of the external alphabet and the values ​​of possible internal states of the automaton - the internal alphabet. Tabular data is the commands that a Turing machine accepts. Problem solving occurs in this way: the letter read by the head in the cell over which it is currently located, and the internal state of the machine’s head determine which command needs to be executed. This particular command is located at the intersection of the external and internal alphabet symbols located in the table.

Components for calculations

To build a Turing machine to solve one specific problem, you need to define the following parameters for it. External alphabet. This is a certain finite set of symbols, denoted by the sign A, the constituent elements of which are called letters. One of them - a0 - must be empty. For example, the alphabet of a Turing device working with binary numbers looks like this: A = (0, 1, a0). A continuous chain of letters and symbols recorded on tape is called a word. An automatic device is a device that operates without human intervention. In a Turing machine, it has several different states for solving problems and, under certain conditions that arise, moves from one position to another. The set of such carriage states is the internal alphabet. It has a letter designation of the form Q=(q1, q2...). One of these positions - q1 - must be the initial one, that is, the one that starts the program. Another necessary element is the q0 state, which is the final state, that is, the one that ends the program and brings the device to the stop position.

Transition table.

This component is an algorithm for the behavior of the device carriage depending on the current state of the machine and the value of the read symbol.-

Algorithm for the machine

During operation, the carriage of the Turing device is controlled by a program that, during each step, performs a sequence of the following actions: Writing a symbol of the external alphabet to a position, including an empty one, replacing the element that was in it, including an empty one. Move one cell step to the left or right. Changing your internal state. Thus, when writing programs for each pair of characters or positions, it is necessary to accurately describe three parameters: ai - an element from the selected alphabet A, the direction of the carriage shift ("←" to the left, "→" to the right, "dot" - no movement) and qk - new state of the device. For example, command 1 “←” q2 has the meaning “replace the character with 1, move the carriage head to the left one step-cell and make a transition to state q2”.