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 simple description and carrying out 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 of entry and exit, and as 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”.

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.

What is it and who created it

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:

1. Unlimited feed. It is infinite in both directions and is divided into cells.
2. 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:

1. 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.
2. Clarity. The device performs only one action for one cell. It enters a character from the alphabet and makes one movement: left or right.
3. 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.
4. 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.
5. Mass character. Each device is defined over the valid words included in the alphabet.

Functions of a Turing machine

In solving algorithms, function implementation is often required. 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 Turing device alphabet for 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 Turing device carriage is controlled by a program that performs the following sequence of actions during each step:

1. Writing a character of an external alphabet to a position, including an empty one, replacing the element that was in it, including an empty one.
2. Move one cell step to the left or right.
3. Changing your internal state.

Thus, when writing programs for each pair of characters or positions, it is necessary to accurately describe three parameters: a i - an element from the selected alphabet A, the direction of the carriage shift ("←" to the left, "→" to the right, "dot" - no movement) and q k - new state of the device. For example, command 1 “←” q 2 has the meaning “replace the character with 1, move the carriage head to the left one cell step and make a transition to state q 2”.

Turing machine: examples

Example 1. The task is given to construct an algorithm that adds one to the last digit of a given number located on a tape. Input data - a word - digits of an integer decimal number, written into consecutive cells on tape. Initially, the device is located opposite the rightmost symbol - the digit of the number.

Solution. If the last digit is 9, then it must be replaced with 0 and then added one to the previous character. The program in this case is for of this device Turing can be written like this:

Here q 1 is the state of digit change, q 0 is stop. If in q 1 the machine fixes an element from the row 0..8, then it replaces it with one of 1..9, respectively, and then switches to the state q 0, that is, the device stops. If the carriage fixes the number 9, it replaces it with 0, then moves to the left, stopping in the state q 1. This movement continues until the device registers a number less than 9. If all characters are equal to 9, they are replaced with zeros, a 0 is written in place of the highest element, the carriage moves to the left and a 1 is written to an empty cell. The next step will be the transition to state q 0 - stop.

Example 2. A series of symbols representing opening and closing parentheses is given. It is required to build a Turing device that would remove a pair of mutual brackets, that is, elements located in a row - “()”. For example, the initial data: “) (() (()”, the answer should be: “) . . ((”. Solution: the mechanism, being in q 1, analyzes the leftmost element in the line.

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

State q 2: the bracket “(” is analyzed for the presence of pairing; if there is a match, the result should be “)”. If the element is paired, then do a carriage return to the left and go to q 3.

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

Who, having borrowed the idea from Emil Post, came up with it, it is believed, in 1936. Despite the rather complex formal definition, the idea is simple in principle. To understand it, let's take a stroll through the pages of Wikipedia.

First of all, we get to the page, which, in fact, is called: “Turing machine”.

Turing machine

Turing machine (MT)- a mathematical abstraction representing a general computing machine. It was proposed by Alan Turing in 2010 to formalize the concept of an algorithm.

A Turing machine is an extension of the finite state machine model and, according to the Church–Turing thesis, is capable of simulating (given the appropriate program) any machine whose action is to move from one discrete state to another.

The Turing Machine includes an infinite in both directions ribbon, divided into cells, and control device with a finite number of states.

The control device can move left and right along the tape, read and write characters of some finite alphabet into cells. Stands out special empty a symbol that fills all the cells of the tape, except those of them (the final number) on which the input data is written.

The control device contains transition table, which represents the algorithm, realizable given Turing Machine. Each rule from the table instructs the machine, depending on the current state and the symbol observed in the current cell, to write a new symbol into this cell, go to a new state and move one cell to the left or right. Some Turing Machine states can be labeled as terminal, and going to any of them means the end of the work, stopping the algorithm.

A Turing machine is called deterministic, if each combination of state and ribbon symbol in the table corresponds to at most one rule, and non-deterministic otherwise.

So, a Turing machine is a mathematical abstraction, a speculative construction of the human mind: it does not exist in nature. Or is there? What immediately comes to mind is how a living cell works. At least two examples.

1. To produce proteins in a cell, using a complex enzyme - RNA polymerase - information is read from DNA, a kind of Turing machine information tape. Here, however, the cells of the tape itself are not rewritten, but otherwise the process is very similar: RNA polymerase sits on DNA and moves along it in one direction, while it synthesizes a strand of RNA - a nucleic acid similar to DNA. The finished RNA, when detached from the enzyme, carries information to the cellular organelles in which proteins are produced.

2. The process of correcting errors in DNA is even more similar to a Turing machine - its repair. Here, DNA polymerase, together with other proteins, moves along the DNA tape and reads both halves of it (genomic DNA, as is known, is two intertwined strands that carry the same information). If the information in the halves does not match, DNA polymerase takes one of them as a sample and “corrects” the other.

This analogy is not new, and on Wikipedia it is also described in the article “Molecular computer":

molecular computer

Biomolecular Computing or molecular computers or even DNA - or RNA - computing - all these terms appeared at the intersection of such diverse sciences as molecular genetics and computer technology.

Biomolecular computing is a collective name for various techniques related in one way or another to DNA or RNA. In DNA computing, data is represented not in the form of zeros and ones, but in the form of a molecular structure built on the basis of the DNA helix. The role of software for reading, copying and managing data is performed by special enzymes.

The basis of the entire biological information storage system, and therefore of DNA computers, is the ability of hydrogen atoms included in nitrogenous compounds (adenine, thymine, cytosine and guanine), under certain conditions, to attract each other, forming non-valently bonded pairs. On the other hand, these substances can valence bond with combinations of a sugar molecule (deoxyribose) and phosphate, forming so-called nucleotides. Nucleotides, in turn, easily form polymers tens of millions of bases long. In these supermolecules, phosphate and deoxyribose play the role of a supporting structure (they alternate in the chain), and nitrogenous compounds encode information.

The molecule turns out to be directional: it starts with a phosphate group and ends with deoxyribose. Long DNA chains are called strands, short ones are called oligonucleotides. Each DNA molecule corresponds to another DNA - the so-called Watson-Crick complement. It has the opposite direction than the original molecule. The attraction of adenine to thymine and cytosine to guanine results in the famous double helix, which allows DNA to double during cell reproduction. The doubling problem is solved with the help of a special enzyme protein - polymerase. Synthesis begins only if a piece of its complement is attached to DNA. This property is actively used in molecular biology and molecular computing. At its core, DNA+polymerase is an implementation of a Turing machine, consisting of two tapes and a programmable control panel. The console reads data from one tape, processes it according to some algorithm and writes it to another tape. The polymerase also sequentially reads the initial data from one tape (DNA) and on its basis forms a tape as if with the results of calculations (Watson-Crick addition).

Slightly fantastic prospects only fuel our curiosity. Meanwhile, we have not yet figured out everything about the Turing machine. As you remember, in the Wikipedia article it was called an extension of the finite state machine. What is a finite state machine? Fortunately, a link is provided to it. Going through it, we find out that:

State machine

Abstract automata form a fundamental class of discrete models, both as a model in their own right, and as a fundamental component of Turing machines, store-memory automata, finite state machines, and other information transformers.

With each definition we intrude more and more into the realm of pure mathematics. The language becomes stricter, formal definitions appear, consisting of mathematical symbols. If we move further, we will come to the theory of algorithms and the theory of computability. You can travel through the pages of Wikipedia for a long time, but it is better to stock up on water and food in case you wander into the desert of axioms and definitions, or at least reliable links to mathematics textbooks, for example http://www.mccme.ru/free-books/, or articles from Potential magazine ;)

I hope this explanation makes it a little clearer to you what exactly a Turing machine is?

Let's go back to the history of this term.

So, as we already mentioned, Alan Turing told the world about his machine in 1937 in the so-called Church-Turing Thesis. The article “Alan Turing” will tell us about Alan Turing, the first hacker and pioneer of computer science, as written on the memorial plaque in the hotel where he was born. We will not give the full text of the article here, but it itself is not very detailed.

Alan Turing

Turing, Alan Matheson(23 June 1912 - 7 June 1954) - English mathematician, logician, cryptographer, inventor of the Turing Machine.

The article itself has more about Turing’s work: in addition to the text about the Turing machine, which we will give later, it is said that he worked on the “freezing problem” (Funny, isn’t it? There were no computers yet, and Windows systems too, but there was already a freezing problem.); the heroic story of how Turing cracked the Enigma code during World War II and thereby saved Great Britain; the fact that he is the founder of the theory artificial intelligence, as well as a mention of the famous Turing test. Nowadays this test is no longer so often used as the premise of a science fiction story, but the problem of the human in the machine will always remain a classic, like the novels of Isaac Asimov and Stanislaw Lem.

Despite its old-fashioned nature, the Turing test made an unexpected appearance in modern world communication over the Internet. For example, you can come across the text of a dialogue between two ICQ users, one of whom is a “bot”, and the task is to determine which one. Or an unfamiliar user, perhaps an ICQ robot, may knock on your door. Do you recognize him? By studying the theory, you may be able to apply the Turing test in time and not be deceived. You can start your study with the corresponding Wikipedia article, and then follow the links provided at the end of the article:

Turing test

Turing test- a test proposed by Alan Turing in 1950 in the article “Computing machinery and intelligence” to test whether a computer is intelligent in the human sense of the word.

The judge (human) corresponds in natural language with two interlocutors, one of whom is a person, the other is a computer. If the judge cannot reliably determine who is who, the computer has passed the test. It is assumed that each of the interlocutors strives to be recognized as a person. In order to make the test simple and universal, correspondence is reduced to text messaging.

Correspondence should occur at controlled intervals so that the judge cannot draw conclusions based on the speed of responses. (In Turing's time, computers reacted slower than humans. Now this rule is necessary because they react much faster than humans.)

The test was inspired by a parlor game in which guests tried to guess the gender of a person in another room by writing questions and reading the answers. In Turing's original formulation, the person had to pretend to be a person of the opposite sex, and the test lasted 5 minutes. These rules are not currently considered necessary and are not part of the test specification.

Turing proposed a test to replace, in his opinion, the meaningless question “can a machine think?” to a more specific one.

Turing predicted that computers would eventually pass his test. He believed that by 2000, a computer with 1 billion bits of memory (about 119 MB) would be able to fool judges 30% of the time in a 5-minute test. This prediction did not come true. (True, at the first Lebner competition computer program"PC Therapist" on an IBM PC 386 was able to fool 5 out of 10 judges, but was not awarded the result, and in 1994 the competition was made more difficult.) Turing also predicted that the phrase "thinking machine" would not be considered an oxymoron, and that computer training would play an important role in creating powerful computers(with which most modern researchers agree).

So far, no program has come close to passing the test. Programs like ELIZA sometimes made people believe they were talking to a person, as in an informal experiment called AOLiza. But such “successes” do not constitute passing the Turing test. First, the person in such conversations had no reason to believe that he was talking to the program, while in a real Turing test the person is actively trying to determine with whom he is talking. Second, the documented cases tend to be in chat rooms such as IRC, where many conversations are fragmentary and meaningless. Third, many IRC users use English as a second or third language, and a program's nonsensical response is likely to be attributed to a language barrier. Fourth, many users know nothing about Eliza and similar programs and cannot recognize the completely inhuman errors that these programs make.

Every year there is a competition between talking programs, and the most human-like, in the opinion of the judges, is awarded the Loebner Prize. There is an additional prize for the program that the judges think will pass the Turing test. This prize has not yet been awarded.

The A.L.I.C.E program showed the best result in the Turing test. winning the test 3 times (in 2000, 2001 and 2004).

Links

• Turing A. M. Computing machines and intelligence. // In: Hofstader D., Dennett D. The Eye of the Mind. - Samara: Bakhrakh-M, 2003. - pp. 47-59.
• Book in English: Roger Penrose “The Emperor’s New Mind”.
• Article by Alan Turing:
  • Alan Turing, “Computing Machinery and Intelligence,” Mind, vol. LIX, no. 236, October 1950, pp. 433-460.
  • Online:
• Article by G. Oppy and D. Dowe on the Turing test from the Stanford Encyclopedia of Philosophy (in English)
• "Turing Test: 50 Years Later" reviews 50 years of work on the Turing Test, from the perspective of the year 2000.

Let's return again to the Turing machine. An excerpt from an article about Alan Turing states that the concept of a Turing machine was first proposed as part of the so-called. Church-Turing thesis:

Excerpt from Wikipedia article "Alan Turing"

Any intuitively computable function is partially computable, or, equivalently, computable by some Turing machine.

Alan Turing proposed (known as the Church-Turing Thesis) that any algorithm in the intuitive sense of the word can be represented by an equivalent Turing machine. Clarification of the concept of computability based on the concept of a Turing machine (and other equivalent concepts) opened up the possibility of rigorously proving the algorithmic unsolvability of various mass problems (that is, problems of finding a unified method for solving a certain class of problems, the conditions of which can vary within certain limits). The simplest example of an algorithmically unsolvable mass problem is the so-called algorithm applicability problem (also called the stopping problem). It consists of the following: it is required to find a general method that would allow, for an arbitrary Turing machine (specified by its program) and an arbitrary initial state of the tape of this machine, to determine whether the operation of the machine will be completed in a finite number of steps, or will continue indefinitely.

In an article called “The Church-Turing Thesis” they write about him like this:

Church-Turing thesis

Church-Turing thesis- a fundamental statement for many fields of science, such as computability theory, computer science, theoretical cybernetics, etc. This statement was made by Alonzo Church and Alan Turing in the mid-1930s.

In its most general form, it states that any intuitively computable function is partially computable, or equivalently, computable by some Turing machine.

The Church-Turing thesis cannot be rigorously proven or disproved because it establishes an "equality" between the strictly formalized notion of a partially computable function and the informal notion of an "intuitively computable function."

Church-Turing physics thesis reads: Any function that can be computed by a physical device can be computed by a Turing machine.

From this crossroads one can move towards, for example, the theory of computability. Or you can try to find out who this mysterious Church is, with whom Alan Turing put forward his thesis.

Universal Turing machine

Universal Turing machine called a Turing machine, which can replace any Turing machine. Having received a program and input data as input, it calculates the answer that a Turing machine whose program was given as input would have calculated from the input data.

Formal definition

The program of any deterministic Turing machine can be written using some finite alphabet consisting of state symbols, parentheses, arrows, etc.; let's denote this machine alphabet as Σ 1 (\displaystyle \Sigma _(1)). Then the universal Turing machine U for the alphabet class of cars Σ 2 (\displaystyle \Sigma _(2)) And k input tapes is called a Turing machine with k+1 entrance tape and alphabet Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1)\cup \Sigma _(2)) such that if you apply for the first k tapes the input value, and on k+1 is the correctly written code of some Turing machine, then U will produce the same answer as it would produce with this input data M 1 (\displaystyle M_(1)), or will work indefinitely if M 1 (\displaystyle M_(1)) will not stop with these data.

Theorem about universal machine Turing asserts that such a machine exists and simulates other machines with no more than a quadratic slowdown (that is, if the original machine produced t steps, then the universal one will produce no more ct 2). The proof of this theorem is constructive (it is not difficult to build such a machine, you just need to carefully describe it). The theorem was proposed and proven by Turing in 1936-37.

Software implementation in the Delphi programming language is quite simple. One of these implementations can be found on the website http://kleron.ucoz.ru/load/24-1-0-52. It is possible to download and save to an Excel file.

Non-deterministic Turing machine

Probabilistic Turing machine

A generalization of a deterministic Turing machine, in which, from any state and values ​​on the tape, the machine can make one of several (we can count, without loss of generality, two) possible transitions, and the choice is made probabilistically (by tossing a coin).

A probabilistic Turing machine is similar to a non-deterministic Turing machine, but instead of a non-deterministic transition, the machine chooses one of the options with some probability.

There is also an alternative definition:

A probabilistic Turing machine is a deterministic Turing machine that additionally has a hardware source of random bits, any number of which, for example, it can “order” and “load” onto a separate tape and then use in calculations in the usual way for MT.

The class of algorithms that complete in polynomial time on a probabilistic Turing machine and return an answer with an error of less than 1/3 is called the BPP class.

One of the most important questions in modern computer science is whether there is a formal performer with which one can imitate any formal performer. the answer to this question was obtained almost simultaneously by two outstanding scientists - A. Turing and E. Post. The performers they proposed differed from each other, but it turned out that they could imitate each other, and most importantly, imitate the work of any formal performer.

What is a formal executor? What does it mean - one formal performer imitates the work of another formal performer? If you played computer games— objects on the screen unquestioningly obey the player’s commands. Each object has a set of valid commands. At the same time, the computer itself is a performer, and not a virtual one, but a real one. So it turns out that one formal performer imitates the work of another formal performer.

Consider the operation of a Turing Machine.

A Turing machine is an endless tape divided into cells and a carriage (reading and printing device) that moves along the tape.

Thus, the Turing Machine is formally described by a set of two alphabets:

A=(a1, a2, a3, …, an) - external alphabet, used to record source data

Q=(q1, q2, q3,…, qm) - internal alphabet, describes a set of states of the reading-printing device.

Each cell of the tape can contain a character from the external alphabet A = (a0,a1,…,an) (In our case A=(0, 1))

The allowed actions of a Turing Machine are:

1) write any symbol of the external alphabet into a cell of the tape (the symbol that was there before is overwritten)

2) move to an adjacent cell

3) change the state to one of those indicated by the internal alphabet symbol Q

A Turing machine is an automaton that is controlled by a table.

The rows in the table correspond to the symbols of the selected alphabet A, and the columns correspond to the states of the machine Q = (q0,q1,…,qm). At the beginning of operation, the Turing machine is in state q1. State q0 is the final state; once in it, the machine ends its operation.

Each cell of the table corresponding to some symbol ai and some state qj contains a command consisting of three parts
· character from the alphabet A
· direction of movement: “>” (right), “<» (влево) или «.» (на месте)
· new state of the machine

In the above table, the alphabet A =(0, 1, _) (contains 3 characters) and the internal alphabet Q=(q1, q2, q3, q4, q0), q0 is the state that causes the carriage to stop.

Let's consider several solutions to problems. You can download the Turing machine on the website in the DOWNLOAD section.

Problem 1. Let A=(0, 1, _). On the tape, the cells contain characters from the alphabet in the following order: 0011011. The carriage is located above the first character. It is necessary to create a program that will replace 0 with 1, 1 with 0 and return the carriage to its original position.

Now let's define the carriage states. I call them “carriage desires to do something.”

q1) The carriage should go to the right: if it sees 0, it changes it to 1 and remains in the q1 state, if it sees 1, it changes it to 0 and remains in the q1 state, if it sees _, it returns back to 1 cell “wants something else” , i.e., goes into state q2. Let's write down our reasoning in the performer's table. For syntax, see the program help)

q2) Now let’s describe the “carriage desire” q2. We must return to our original position. To do this: if we see 1, we leave it and remain in state q2 (with the same desire to reach the end of the series of symbols); if we see 0, we leave it and continue to move left in state q2; we see _ - moves to the right by 1 cell. Now you are where it is required in the task conditions. we go to state q0.

You can watch the program in action on the video:

Problem 2. Given: a finite sequence of 0 and 1 (001101011101). It is necessary to write them out after this sequence, through an empty cell, and in this sequence replace them with 0. For example:

From 001101011101 we get 000000000000 1111111.

As you can see, seven units were written after this sequence, and in their places there are zeros.

Let's start the discussion. Let's determine which states the carriage needs and how many.

q1) saw 1 - correct it to zero and go to another state q2 (a new state is introduced so that the carriage does not change all ones to zeros in one pass)

q2) don't change anything, move to the end of the sequence

q3) as soon as the carriage sees an empty cell, it takes a step to the right and draws a 1, if it sees a 1, it moves on to sign the symbol at the end. As soon as I have drawn a unit, we go to state q4

q4) we go through the written units without changing anything. As soon as we reach an empty cell separating the sequence from ones, we move to a new state q5

q5) in this state we go to the beginning of the sequence without changing anything. We reach an empty cell, turn around and go to state q1

The carriage will assume state q0 in the case when it passes in state q1 to the end of this sequence and encounters an empty cell.

We get the following program:

You can watch the Turing Machine in action in the video below.

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.

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 d (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 i) into a triple of the Cartesian product Q x Г x (L,R) (the machine goes to state qi, replaces character i with character j and moves left or right one tape character) - 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 U є Г - Si є У onto tape:

eS1S2S3S4... ... ...Sne

after which the machine is transferred to the initial state and the head is installed at the leftmost non-blank 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.

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.