What was the significance of the Turing machine? Turing machine: description and examples of Turing machines

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 neither was the Windows system, 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 of 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 has emerged in an unexpected way in the modern world of Internet communication. 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 Loebner competition, the computer program “PC Therapist” on an IBM PC 386 was able to mislead 5 out of 10 judges, but its result was not credited, and in 1994 the competition was made more difficult.) Turing also predicted that the combination “thinking machine” would not be considered an oxymoron, and computer training would play an important role in creating powerful computers (which most modern researchers agree with).

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).

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.

The Universal Turing Machine Theorem states that such a machine exists and models other machines with at most 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.

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.

Turing machine (MT)- abstract performer (abstract computing machine). Was suggested Alan Turing V 1936 to formalize the concept algorithm.

Turing machine is an extension finite state machine and, according to Church-Turing thesis, is capable of simulating all other executors (by specifying transition rules) that somehow implement the step-by-step calculation process, in which each calculation step is quite elementary.

Turing machine design

The Turing machine is infinite in both directions. ribbon(Turing machines are possible that have several infinite tapes), divided into cells, and control device, capable of being in one of set of states. The number of possible states of the control device is finite and precisely specified.

The control device can move left and right along the tape, read and write symbols of some finite alphabet into the cells of the tape. 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 operates according to transition rules, which represent the algorithm, realizable this Turing machine. Each transition rule instructs the machine, depending on the current state and the symbol observed in the current cell, to write a new symbol into this cell, move 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. If there is a "ribbon symbol - state" pair for which there are 2 or more instructions, such a Turing machine is called non-deterministic .

Description of the Turing machine

A specific Turing machine is defined by listing the elements of the set of letters of the alphabet A, the set of states Q, and the set of rules by which the machine operates. They have the form: q i a j →q i1 a j1 d k (if the head is in the state q i, and the letter a j is written in the observed cell, then the head goes to the state q i1, a j1 is written in the cell instead of a j, the head makes a movement d k, which has three options: one cell to the left (L), one cell to the right (R), stay in place (N)). For every possible configuration there is exactly one rule. There are no rules only for the final state, once in which the car stops. In addition, you must specify the final and initial states, the initial configuration on the tape, and the location of the machine head.

An example of a Turing machine

Let's give an example of MT for multiplying numbers in unary number system. The machine operates according to the following set of rules:

Set of rules	Set of rules


q 0 ×→q 1 ×R



	q 6 ×→q 7 ×R
q 2 ×→q 3 ×L
q 3 1 → q 4 aR


q 4 ×→q 4 ×R

Let's multiply using MT 3 by 2 in the unit system:

The protocol indicates the initial and final states of the MT, the initial configuration on the tape and the location of the machine head (underlined symbol).

Turing completeness

Main article: Turing completeness

We can say that a Turing machine is the simplest computing machine with linear memory, which, according to formal rules, transforms input data using a sequence elementary actions.

The elementary nature of actions lies in the fact that the action changes only a small piece of data in memory (in the case of a Turing machine, only one cell), and the number of possible actions is finite. Despite the simplicity of the Turing machine, it can calculate everything that can be calculated on any other machine that performs calculations using a sequence of elementary actions. This property is called completeness.

One natural way to prove that computational algorithms that can be implemented on one machine can be implemented on another is to simulate the first machine on a second.

The imitation is as follows. A description of the program (operating rules) of the first machine is supplied to the input of the second machine. D and input data X, which should have arrived at the input of the first machine. It is necessary to describe such a program (rules for the operation of the second machine) so that as a result of the calculations the output turns out to be the same as what the first machine would return if it received data as input X.

As was said, on a Turing machine it is possible to simulate (by specifying transition rules) all other executors that somehow implement the process of step-by-step calculation, in which each step of the calculation is quite elementary.

On a Turing machine you can simulate Post's car, normal Markov algorithms and any program for ordinary computers that converts input data into output data using some algorithm. In turn, a Turing Machine can be simulated using various abstract executors. Performers for whom this is possible are called Turing complete(Turing complete).

There are programs for ordinary computers that simulate the operation of a Turing machine. But it should be noted that this simulation is incomplete, since the Turing machine contains an abstract infinite tape. An endless tape with data cannot be fully simulated on a computer with finite memory (the total computer memory - RAM, hard drives, various external storage media, registers and processor cache, etc. - can be very large, but, nevertheless, always finite).

Turing machine variants

The Turing machine model can be extended. One can consider Turing machines with an arbitrary number of tapes and multi-dimensional tapes with various restrictions. However, all of these machines are Turing complete and are modeled by an ordinary Turing machine.

Turing machine running on a semi-infinite tape

As an example of such information, consider the following theorem: For any Turing machine, there is an equivalent Turing machine running on a semi-infinite tape.

Let's consider the proof given by Yu. G. Karpov in the book “Theory of Automata”. The proof of this theorem is constructive, that is, we will give an algorithm by which for any Turing machine an equivalent Turing machine with the declared property can be constructed. First, we randomly number the cells of the MT work tape, that is, we determine a new location of information on the tape:

Then we renumber the cells, and we will assume that the symbol “*” is not contained in the MT dictionary:

Finally, let's change the Turing machine by doubling the number of its states, and change the shift of the read-write head so that in one group of states the operation of the machine would be equivalent to its operation in the shaded zone, and in another group of states the machine would work as the original machine works in the unshaded area. If the ‘*’ symbol is encountered during MT operation, it means the read-write head has reached the zone boundary:

The initial state of the new Turing machine is set in one or the other zone, depending on where in the original tape the read-write head was located in the original configuration. Obviously, to the left of the bounding markers "*" the tape is not used in an equivalent Turing machine.

I decided to explain to humanity the principle of algorithmic calculations. The fact is that Mr. Turing was a prophet of the computer age, so he simply could not help but tell people what an algorithm is. So he came up with an abstract machine that was named after him. That is, the last name. But let's take it in order...

The essence in simple words

An important point should be immediately noted: a Turing machine is an exclusively speculative device. Nothing like this exists in nature. There are computer models, however. Even active ones. But they are nothing more than models.

Why is that? Because the subject of discussion is an endless tape, the full physical existence of which at this stage of the development of science and technology is possible only theoretically.

The tape consists of cells, like a chain of links. The cells contain data, for example, alphabet characters. Well, or zeros and ones. In general, anything suitable for automatic processing. This is performed by a moving part of the machine.

How it works

The moving part is the reader and writer. Some kind of contraption capable of reading the contents of cells, writing something of its own into them and, most importantly, acting in accordance with the resulting results.

Moreover, the machine can only move one cell at a time. Right, left, wherever necessary to perform calculations. Here you added something - you need to move in order to take something away. And then fold it again. And so on for as long as necessary until the task is completed. The tape is endless, there are enough options for any operation.

As a matter of fact, Alan Turing was precisely trying to emphasize that every calculation, no matter how complex, can be performed in stages, step by step, breaking the problem into elementary components. This is the essence of the algorithm.

Different variants

Novice cybernetics looked at the Turing machine and realized that there was nothing to complain about. Indeed, computer programs should be built on the basis of algorithms - step-by-step execution of instructions.

At the same time, the fame of Alan Turing haunted many, and followers began, as they say, to catch glimpses of it. They began to invent multidimensional Turing machines, with many tapes, “semi-infinite” ones, etc.

We will try to bring at least some clarity to this chaos and consider real options for the device under discussion.

Non-deterministic- this is a Turing machine that operates on the above-described tape with cells in accordance with the situation that arises at a particular stage of calculations. Where she needs to go, that’s where she will go, in other words.
Deterministic- one that contains specific instructions. For example, if the letter A is written in the cell where the executing machine is located, then you need to move to the adjacent one, with the letter B, whether you want to or not.
Full- capable of calculating everything that can be calculated by step-by-step operations. It can even simulate a machine in a machine, an emulator that describes with algorithms the operation of another similar device.
Universal- capable of everything that any variant of a Turing machine can do. In general, any, even not yet invented. Of course it is complete.

Practical benefits

Of course, an algorithm is a more complex concept than simply moving execution step by step in one-dimensional space. After all, branching, looping, going back, and using subroutines are possible.

In addition, it is impossible in practice to simulate an infinite number of cells containing data, if only because the capabilities of computer equipment are limited.

However, there are programs that simulate Turing machines designed for teaching students. Beginning programmers are encouraged to develop different algorithms, for example, searching, changing, adding, rearranging letters in cells.

Consequently, the benefits of the Turing machine are exactly as intended by its creator, the prophet of the computer age: a clear demonstration of the essence of algorithmic calculations.

Previous publications:

Last edit: 2013-04-01 10:58:05

Material tags: ,

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:

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

News

Falina I.N. The topic “Turing Machine” in the school computer science course (inf.1september.ru).
Mayer R.V. Post and Turing machines (komp-model.narod.ru).
Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Turing machine and Markov algorithms. Problem solving, M.: MSU, 2006.
Bekman I.N. Computer science. Lecture 7. Algorithms (profbeckman.narod.ru)
Soloviev A. Discrete mathematics without formulas (lib.rus.ec)
Ershov S.S. Elements of the theory of algorithms, Chelyabinsk, SUSU Publishing Center, 2009.
Varpakhovsky F.L. Elements of the theory of algorithms, M: Prosveshchenie, 1970.
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) publication of materials in any form, including posting of materials on other Web sites;
2) distribution of incomplete or altered materials;
3) inclusion of materials in collections on any media;
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.

Also on topic

Air filter description types device operating principle photo video

The cruiser "Aurora" returned to its original place under its own power. What changed on the "Aurora" during the repair

Air filter Toyota Camry

Disadvantages of LED headlights