What is a Turing machine and how does it relate to programming?

Question

Programming

Turing machine. Endless tape. A head that can move, write and read. OK. What is all this for and what does it all mean?

Answer 1

First of all, this is a formal definition of the algorithm. A problem is said to be algorithmically solvable if and only if its solution can be programmed on a Turing machine (or in some other equivalent way). This definition makes it possible, for example, to present algorithmically unsolvable problems. Allows you to introduce the concept of a "Turing-complete" language - if a Turing machine can be implemented in a language, then any algorithm can be written on it (C is not such a language, but C # is).
In general, MT is a way to define a certain class of algorithms:
- some problems can be solved by a finite automaton;
- some will require a state machine with stack memory;
- for others, a Turing machine is sufficient;
- the rest require divine revelation or other non-algorithmic methods.

Answer 2

A Turing machine is the simplest device that implements actions according to an algorithm that takes into account the current state of the device and the state of the current memory cell (traditionally they speak of a "tape"). In the case of a so-called deterministic (that is, defined) Turing machine, each pair of device and current cell states corresponds to a single elementary action (which may include moving through memory and changing the state of cells).
This theory is used to study the principles of constructing formal algorithms using the simplest abstract example.

Answer 3

That any computer is a terribly overcomplicated Turing machine, though with a finite tape.
It is easier to study the fundamental theory of algorithms on such a pretentiously elementary computer, which is guaranteed to be realizable.

Answer 4

It is strange that you do not dig to the computer at all. After all, in fact, any computing device is 2 instructions. One is NOT and the other is either AND or OR. ALL computing devices are built on these two NAND or NOR!

Answer 5

Well, the movie recently came out The Imitation Game - the whole movie is about this car. Look and you will understand. And for programming, in my opinion, only one word is appropriate here - algorithms!

Answer 6

MT gives an idea of ​​what an algorithm is.

Answer 7

This was used to break enigma into the Second World War. This is the basis of the von Neumann architecture on which ENIAC was built and all computers after. This is an extension of the state machine, which is embedded in any controller, which is implemented in any parser, lexer and compiler.