What is the Turing machine?

Asked

Viewed 28,267 times

13

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?

  • Where he is known as the father of computing ?

  • https://www.google.com/search?q=pai+da+ca&oq=pai+da+ca&aqs=chrome..69i57.2527j0j7&sourceid=chrome&ie=UTF-8 But I believe the most correct term would be the father of modern cryptography :)

  • 2

    Is it duplicate of this? (who considered duplicate and I thought it is not, but I will not handle it on my own) http://answall.com/q/102452/101. Related or at least bearing practical references: http://answall.com/q/101683/101, http://answall.com/q/35547/101, http://answall.com/q/99642/101, http://answall.com/q/46983/101, http://answall.com/q/7740/101, http://answall.com/q/81854/101, http://answall.com/q/113985/101, http://answall.com/q/28297/101, http://answall.com/q/30749/101, among others

  • 2

    The question is good, but I think it is duplicate yes :P

  • 3

    I believe the term is used a lot as a poetic license. It is complicated to make such a statement when in fact several people have contributed much to the basis of modern computing, one without the other would be of no use at all to what we have today.

  • 1

    @bigown I think that your answer http://answall.com/a/35548/14262 has already answered that question

  • Maybe what saves the question is "How does it work and how does it read a binary tape?"

  • @Marcelobonifazio do not know, let’s see what other people think, It may be that can come out something more specific. Maybe the second part can fit alone.

  • I agree that the question is good (the functional part)... And taking into account the placement of @bigown, I’m comfortable with the term "one of the parents"...

  • Just remembering that the machine of Turing corroborated for the creating one of the most important and complex areas of computing (), since he is considered "one of the" fathers of modern computing, it is not possible to attribute the whole state of the art to him alone, we had other great minds in the evolution of computing, see George Boole, Von_neumann, among others

  • @bigown I think the closest those answers should be is one that says language has to obey a Turing machine, but what it is and how it works I don’t think those questions answer. Marcelobonifazio, I think father refers to the idea of being one... but I agree that there may be controversies to this title and that it is controversial

  • For those who like to watch Faustão on Sunday, the tip : https://www.youtube.com/watch?v=eqzuLlY6cJA

  • http://morphett.info/turing/turing.html

  • This is an encyclopedic question, I don’t think it’s part of the scope of the O.R..

Show 9 more comments

1 answer

14


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:

inserir a descrição da imagem aqui

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.

  • 1

    Well explained the functional part, just do not understand the relationship between the final title and the content, The big problem (in my view) of the statement is in the definition of the word "computation", and in this way its predecessors such as : Panini (500.ac), Wilhelm Schickard, Joseph Marie Jacquard, Charles Babbage, Blaise Pascal, the Babylonians among others, in my view, suffer total injustice. It would be like saying that the Father of wireless communication is Marconi and not Tesla... Keeping the proper proportions...

Browser other questions tagged

You are not signed in. Login or sign up in order to post.