Alan Turing Brasil 2012

Exhibition Lectures Video Contest Code Breaker Culture

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 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 to 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 set of instructions known and processed by the finite control module is listed below

PRINT 0 IN THE SQUARE THAT PASSING THE HEAD
PRINT 0 IN THE SQUARE THAT PASSING THE HEAD
GO TO LEFT FRAME
GO TO RIGTH FRAME
GO TO STEP i IF the frame that pass over head count 0
GO TO STEP j IF the frame that pass over head count 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 , »)

2 ( s0 , 0, s1 , 1)

3 ( s1 , 1, s1 , «)

4 ( s1 , 0, s2 , »)

Algorithm 1: Example of instructions between the three states s0, s1 e 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 ', move the head to the right and will remain in state s0. Second, if a digit is read '0 'the machine will leave the state s0, s1, and the state will write the digit '1' in this transition. The instructions in lines 3 and 4 show what happens in state s1, ie, if read in the digit '1 ', the machine moves its head 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 is effective representation of the machine using a state diagram. Figure 2 represents the set of instructions in a 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), constituted by the first symbol that will be read and then by the action that should be performed with the transition. The symbols belong to the alphabet Σ and the action will be the symbol to be written, or 'or', indicating a movement to the left or right ...

Download this file! Download a copy of Alan Turing paper about computable numbers!

Address:

Country: Brazil: Citty: Porto Alegre; Instituto de Informática; Campus do Vale; Post Box 15064; Phone +55 (51) 3308 6168; Fax +55 (51) 3308 7308; Email:info@ufrgs.br