What is the Turing machine?

Question

What is this such Máquina de Turing that made Turing be recognized as the "Pai da Computação"? How it works and how it reads a binary tape?

Answer 1

What is a Turing machine?

To Turing machine is a theoretical device known as the universal machine, which was designed by the British mathematician Alan Turing (1912-1954), many years before modern digital computers existed (the reference article was published in 1936). In a precise sense, it is an abstract model of a computer, which is restricted only to the logical aspects of its functioning (memory, states and transitions) and not to its physical implementation. A Turing machine can model any digital computer.

A Turing machine consists of:

• A tape that is divided into cells, one adjacent to the other. Each cell contains a symbol of some finite alphabet. The alphabet contains a special white symbol (here written as ) and one or more additional symbols. It is assumed that the tape is arbitrarily extensible to the left and to the right, i.e., the Turing machine has as much tape as is required for computation. Cells that have not yet been written are also assumed to be filled with the white symbol.
• A head, which can read and write symbols on the tape and move left and right.
• A state register, which stores the state of the Turing machine. The number of different states is always finite and there is a special state called the initial state with which the state registrar is initialized.
• An action table (or transition function) that tells the machine which symbol to type, how to move the head ( left and right) and what its new state will be, given the symbol it just read on the tape and the state it is in. If there is no entry in the table for the current symbol and state combination then the machine stops.

Note that each part of the machine is finite; it is its potentially unlimited tape quantity that gives an unlimited amount of storage space.

Functioning

• The Turing machine must always assume in a state, belonging to a finite set of states;
• The processing of a Turing machine always begins in a special state, called the initial state;
• Initially the first cell of the tape is filled with " ", which indicates the beginning of the tape;
• The reading head is initially positioned in the second cell of the tape, the cell following " ";
• Blank cells, which are not part of the word to be processed, are filled with the symbol "β";

• Processing in an MT consists of a sequence of steps consisting of:

  • Note the chain symbol of the tape (the one on which the head is positioned);
  • Write a symbol in this tape cell;
  • Move the head left or right;
  • Change the current state;
  • The exact action to be executed is determined by a program (transition function) that communicates to the control unit what must be done based on the configuration (state + current tape symbol) in which the Turing machine is.

• Processing ends when the machine reaches a configuration for which there is no intended function, in this case:

  • If the machine is in an active final state, the input word is accepted;
  • If the active state is not final, the input word is not accepted;
  • If the machine doesn’t stop (looping), entry is not accepted.

The Turing machine can be used as a model of a recognizing nature or transducer:

• Recognizer: Processes the input word by accepting or rejecting it. In this case, the set of accepted words corresponds to the language described by MT;
• Transducer: machine to compute a function. Applies a function on the initial content of the tape and the produced result is released on the tape itself.

Turing machine representation by diagram:

• Similar to the representation of Deterministic finite automaton;
• The arrow labels, which represent the transition functions are according to the following legend:

Alan Turing, the father of computing

His successful career began during World War II, when he worked for British intelligence at a code-breaking center. The mathematician developed a system called "Bombe", to translate the secret texts of the Germans, generated by cryptographic machines called "Enigma". Bombe translated coded communications by Enigma, transforming them into a true and understandable message.

However, his great achievement was the creation of the Turing machine. An automatic invention capable of manipulating symbols on a tape according to a series of rules for storing information, just as computers do today. Turing developed algorithm concepts - a recipe that shows step by step the procedures necessary for solving a task - and computation. He also "wrote" the first chess computer program. Even with all these inventions, there was still time to devote to chemistry, physics and biology.

Alan Turing also developed the Turing test, created with the aim of verifying whether the computer is capable of imitating and thinking like the human brain, that is, a kind of artificial intelligence with the possibility of deceiving anyone. The test consisted of asking a person to send a series of questions to the computer and, after analyzing the answers given by him, try to differentiate whether the answer given by the system was prepared by the human being or by the machine.