What is Turing Machine?

What is Turing Machine?

The Turing Machineis a theoretical device known as the universal machine, which was conceived 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. On a Turing machine you can model any digital computer.

A Turing machine consists of:

• a ribbon that is divided into cells, one adjacent to the other. Each cell contains a symbol of some finite Alphabet. The alphabet contains a white special symbol (here written as ) and one or more additional symbols. It is assumed that the tape is arbitrarily extensible to the left and right, that is, the Turing machine has as much tape how much is needed for computing. It is also assumed that cells that have not yet been written are filled with the White symbol.
• a headstock, which can read and write symbols on the tape and move left and right.
• a state logger, 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 What symbol to write, how to move the header (←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 combination of symbol and state then the machine stops.

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

Operation

• 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 it;
• The Read head is initially positioned in the second cell from the ribbon, the cell following " 〈";
• blank cells, which are not part of the word to be processed, are filled with the symbol "β";

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

  • observe the current symbol of the tape (the one on which the head is positioned);
  • write a symbol in this ribbon cell;
  • move the head to the left or right;
  • Change State current;
  • the exact action to be performed is determined by a program (transition function) that communicates to the Control Unit what should be done based on the configuration (State + current ribbon symbol) in which the Turing Machine is located.

• 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 end state, the input word is accepted;
  • if the active state is not final, the input word is not accepted;
  • if the machine does not stop (looping), the input input is not accepted.

The Turing machine can be employed as a model of recognisable 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 for computing a function. Applies a function over 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 labels of the arrows, which represent the transition functions are according to the following Legend:

Alan Turing, o parent of computation

His trajectory of success began during World War II, when he worked for British intelligence in a centre specializing in code breaking. The mathematician developed a system called "bombe", to translate the secret texts of the Germans, generated by encryption machines called "Enigma". Bombe translated Communications encoded by Enigma, turning them into a true and understandable message.

But 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 concepts of algorithm-a recipe that shows step by step the procedures necessary for solving a task – and computation. Also "wrote" the first computer chess 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, trying to differentiate whether the answer given by the system was made by human or machine.