Ana səhifə

It is an imaginary device that formed the framework for support of modern computer science


Yüklə 46.5 Kb.
tarix25.06.2016
ölçüsü46.5 Kb.
Turing Machine

It is an imaginary device that formed the framework for support of modern computer science.


Its inventor, the mathematician Alan Mathison Turing showed that computation of the operations of reading, writing and deleting binary symbols could be satisfied by a machine containing a tape of unlimited length, with square size defined on it and a device with a finite number of states, who performed the operations on the tape.

In 1936 the term was formalized algorithm: a finite set of simple and precise instructions, which are described with a finite number of symbols.

"Any process acceptable to us men as an algorithm is precisely what a Turing machine can do" (Alonzo Church, a mathematician).

Turing machines for construction: There were two models that stood out in our research.


1. More complete model, with digital circuits and implementations of several algorithms: http://aturingmachine.com with demo video: http://www.youtube.com/watch?v=E3keLeMwfHY

It is difficult to implement, so ugly was the contact for the exhibition.

2. Using a Lego kit: http://legoofdoom.blogspot.com with demo video: http://www.youtube.com/watch?v=cYw2ewoO6c4

For the first (1), its implementation is easier, but will require a lot of work for her to perform the operations of reading, writing and deleting and perform some simple algorithms such as summation and subtraction. In an address given for details of construction and contact the authors.


  

Material for the Book:

TURING MACHINE

Rogério Xavier de Azambuja

Elias Ramos

November/2011.

It is an imaginary device grounded by a revolutionary theory of its author, Alan Mathison Turing, conceived at 24 years of age. The Turing machine has formed the basic structure to support the modern computer science and computability. Years later was responsible for recognition of the scientific community, declaring the Turing symbolic title "father of computing."
The theory was first published in 1936, an article entitled "On Computable Numbers, with an Application on the Entscheidungsproblem," in response to treatment of the decision problem, formulated by Hilbert. Turing studied at Princeton University, New Jersey, USA.
Despite the Turing machine has not been physically implemented in full by its author, the computational process has been mathematically demonstrated and proven in the article. Turing explained a logical device that he called "automatic machine" (or "a-machine"), can read, write and erase binary symbols on a tape of unlimited length and divided by squares of equal size. A head read / write would move in any direction along the tape, one square at a time, and a control unit could play a list of simple instructions, moving to the right or left. The rule executed determines the so-called state of the machine.

Figure 1: Conceptual model of the Turing machine.

The concept of a Turing machine is similar to a formula or equation. Thus, there is an infinity of possible Turing machines, each corresponding to a defined method or algorithm. Turing proposed that each algorithm, formalized as a finite set of well defined instructions, could be interpreted and executed by a mechanical process.
Formally a Turing machine can be defined as a machine that contains:
• A finite set of states Q with a distinguished initial state,
• A finite set of symbols Σ.
The interpretation and implementation of the algorithms are carried out by states and a transition function determines the new contents of the tape. In this way, a restriction imposed on the algorithm, you can change the contents of only one square at a time or move the head at most one cell in any direction. It also permitted the use of any finite set of symbols for the alphabet Σ, even if the original definition has insisted on Σ = {0,1}. This change has no impact on defining the set of functions computable by the machine.
What makes a Turing machine capable of performing a task is the table of transition rules that comprise the machine and a given initial state. The instruction set known and processed by control module finite, illustrated in Figure 1, is referenced below:
• IN PRINT 0 PASSING BY SQUARE HEAD
• IN PRINT 1 PASSING BY SQUARE HEAD
GO TO SQUARE ONE LEFT
• GO TO SQUARE ONE RIGHT
• i GO TO STEP UP THE HEAD BY PASSING SQUARE CONTAINS 0
• GO TO STEP j IF THE HEAD BY PASSING SQUARE BOX 1
• STOP
For example, a computation can be represented by three states, named s0, s1, s2 and some instructions formalized in Algorithm 1:


  1. s0 , 1, s0 , »⟩

  1. s0 , 0, s1 , 1⟩

  1. s1 , 1, s1 , «⟩

  1. s1 , 0, s2 , »⟩

Algorithm 1: Example of instructions between three states s0, s1 and s2.

The first two statements (lines 1 and 2) describe what happens in state s0. There are two possibilities: first, the machine reads a digit '1 ', movimentará head to the right and will remain in state s0. In the second, if read in a digit '0 'the machine will leave the state s0, s1 enter the state and write the digit '1' in this transition. The instructions on lines 3 and 4 show what happens in state s1, ie, if read in the digit '1 ', the machine movimentará head to the left and remain in state s1. If you read the digit '0 ', the head will be moved to the right and the machine moves to state s2. Since there are no instructions defined by the algorithm in state s2, the machine stops its execution (stop condition) to reach this state.


When we are interested in examining the behavior of a Turing machine, the representation of the machine is effective using a state diagram. Figure 2 represented the set of instructions in this visual format.

Figure 2: A state diagram representing the Algorithm 1.

In this figure, the states are represented by circles, with a double circle identifying the initial state. A transition is represented by an edge or arc from one state to another or to the same state. Edges are labeled by pairs (symbol, action), the first consisting of the symbol should be read and then the action that should be performed with the transition. The symbols belong to the alphabet Σ and the action is the symbol to be written, or even 'or', indicating a movement to the left or right.
Figure 2 illustrates a machine that calculates the successor of n, as a simple execution for purposes merely demonstrative. Thus, the initial state of the ribbon represents the number n after executing the sequence of steps, it will stop the default configuration that represents the number n +1. A possible implementation is demonstrated in Figure 3 (ac).



  1. (b) (c)

Figure 3: Sequence implementation of algorithm 1, from a initial state

.

Today, it is easy to relate a computer program with a Turing machine and the mechanical task of interpretation and implementation obeying the algorithm. Thus, the Universal Turing machine embodies the essential principle of the computer: a simple machine that can perform any task well defined, provided that specified as an appropriate program.


You can also find some modern simulations for conceptual Turing machine. Figure 4 illustrates a mixed model of digital and mechanical components, found in http://aturingmachine.com with demonstration video on http://www.youtube.com/watch?v=E3keLeMwfHY.



Figura 4: Simulação utilizando componentes digitais.
Figure 5 illustrates a simulation using the reference kit Lego, found under http://legoofdoom.blogspot.com, with demo videos contained on http://www.youtube.com/watch?v=cYw2ewoO6c4.

Figure 5: Simulation using reference kit Lego.

Turing proved that for any formal system there is a Turing machine that can be programmed to imitate him. It was this generic formal system, with the ability to imitate any other formal system, which essentially sought to Turing. Such systems are called Universal Turing Machines. The mathematical logician Alonzo Church has come to define it: "Any process acceptable to us men as an algorithm is precisely what a Turing machine can do."
In April 1936, Turing showed their results to John Von Neumann at Princeton, when the computers in the modern sense, did not exist. Turing created the concepts and mathematical foundation, which would be nine years after the technology used to materialize the first electronic computers, with the participation of Neumann, ie the transformation of the logic of their abstract ideas into real engineering. During this time, Turing returned to England and lived only idea in his mind. The correspondence between logical instructions, the action of the human mind and a machine that could be physically built, was the final contribution of Alan Mathison Turing.

References:


Turing machines in Princeton, available at http://introcs.cs.princeton.edu/java/74turing, accessed October 2011.
Turing machines with Stanford, available in http://plato.stanford.edu/entries/turing-machine, accessed October 2011.


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©atelim.com 2016
rəhbərliyinə müraciət