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 machinesfor construction: There were two modelsthat stood outin our research.
1.More complete model, with digital circuitsand implementationsof several algorithms: video:
It isdifficult to implement, so uglywasthe contact for theexhibition.
2. UsingaLegokit: video:
Forthe first(1), its implementation is easier, but willrequire a lot ofwork for herto perform the operationsof reading, writingand deletingand perform somesimple algorithmssuch assummation andsubtraction.Inanaddress givenfordetails ofconstruction andcontact the authors.
Materialfor theBook:
TURING MACHINE
Rogério Xavier de Azambuja
Elias Ramos
November/2011.
It isanimaginarydevicegroundedby arevolutionary theory ofits author,AlanMathisonTuring, conceivedat 24years ofage.The Turing machinehas formedthe basic structureto support themodern computer scienceandcomputability. Years laterwas responsiblefor recognitionof the scientific community, declaring theTuringsymbolic title"father ofcomputing."
The theorywasfirst publishedin 1936, an article entitled"On Computable Numbers,withan Applicationon theEntscheidungsproblem," in response to treatmentof thedecision problem, formulated by Hilbert. Turingstudiedat Princeton University, New Jersey, USA.
Despite theTuring machinehas not beenphysicallyimplementedin fullby its author,the computational processhas beenmathematicallydemonstratedand provenin the article.Turingexplainedalogical device thathe called"automaticmachine"(or"a-machine"), can read, write and erasebinary symbolson a tapeof unlimited lengthand dividedby squaresof equal size.A headread / writewould movein any directionalong the tape, onesquare at a time, and acontrol unitcould playalist ofsimple instructions, moving to the right orleft.The ruleexecuted determines theso-calledstateof the machine.
Figure1: Conceptual model oftheTuring machine.
The conceptof a Turing machineis similar toaformula orequation.Thus, there is aninfinity of possibleTuring machines, each corresponding toa defined methodor algorithm. Turingproposed that eachalgorithm,formalized asafinite set ofwell definedinstructions, couldbe interpretedand executed byamechanical process.
FormallyaTuring machinecan be defined asamachine thatcontains:
•A finite set ofstatesQ withadistinguishedinitial state,
•A finite set ofsymbolsΣ.
The interpretation andimplementationof the algorithmsare carried out bystates andatransition functiondeterminesthe newcontents of the tape. In this way, arestriction imposed on thealgorithm,you can changethe contents of onlyonesquare at a timeormove the headat mostonecell inany direction. Italso permittedthe use of anyfinite set ofsymbolsfor the alphabetΣ, even if theoriginal definitionhasinsisted onΣ={0,1}. This changehas no impacton defining theset of functionscomputableby the machine.
What makesaTuring machinecapable of performinga taskis the tableof transition rulesthat comprisethe machine anda giveninitial state. The instruction setknownand processed bycontrol modulefinite,illustrated inFigure 1, isreferenced below:
•INPRINT0PASSINGBYSQUAREHEAD
•INPRINT1PASSINGBYSQUAREHEAD
•GOTOSQUAREONELEFT
•GOTOSQUAREONERIGHT
•iGOTOSTEPUPTHEHEADBYPASSINGSQUARECONTAINS0
•GOTOSTEPjIF THEHEADBYPASSINGSQUAREBOX1
•STOP
For example,acomputation can berepresented bythree states, nameds0, s1, s2 andsome instructionsformalizedin Algorithm1:
2.⟨s0 , 0, s1 , 1⟩
3.⟨s1 , 1, s1 , «⟩
4.⟨s1 , 0, s2 , »⟩
Algorithm 1: Example of instructions betweenthree statess0, s1 and s2.
The first two statements(lines 1and 2)describewhat happensin states0. There are two possibilities: first, the machinereadsadigit '1 ', movimentaráheadto the right andwill remainin states0. In the second, if read in a digit'0 'the machine will leavethe states0, s1enterthe stateand writethe digit '1'in this transition.The instructionson lines3 and 4 showwhat happensin states1,ie, if read in the digit '1 ', the machine movimentaráhead to theleft andremainin states1. If youread thedigit '0 ', the head will bemoved to the rightand the machinemoves tostates2.Since there are noinstructionsdefinedby the algorithmin states2,the machine stopsits execution(stop condition) to reach this state.
When we areinterested in examiningthe behavior ofaTuring machine, the representation of themachineis effectiveusingastate diagram. Figure 2representedthe set ofinstructions in thisvisual format.
Figure2: A state diagramrepresentingtheAlgorithm 1.
In this figure, the states are represented bycircles, withadouble circleidentifyingthe initial state. A transition isrepresentedby an edgeor arcfromone state toanother orto the same state. Edges arelabeled bypairs (symbol, action), the firstconsistingof the symbolshouldbe read andthentheaction thatshouldbe performed withthe transition. The symbolsbelongto the alphabetΣand theaction isthe symbol to bewritten,or even'or',indicatingamovement to the leftor right.
Figure 2 illustratesa machinethat calculatesthe successorof n,as asimple executionfor purposesmerelydemonstrative.Thus, the initial state of the ribbonrepresents the numbernafter executingthe sequenceof steps, it will stopthedefault configuration thatrepresents the numbern+1. A possibleimplementationis demonstratedin Figure 3(ac).
(a) (b) (c)
Figure 3:Sequenceimplementation ofalgorithm 1,from ainitial state
.
Today, it iseasy to relateacomputer program withaTuring machineand themechanical taskof interpretation andimplementationobeying thealgorithm.Thus, theUniversal Turing machineembodiesthe essential principleof the computer: asimple machine thatcan performany taskwell defined, provided that specified asanappropriate program.
You canalsofindsomemodernsimulationsforconceptualTuring machine. Figure 4 illustratesamixed modelofdigitaland mechanicalcomponents, found in videoon
Figura 4: Simulação utilizando componentes digitais.
Figure 5 illustratesa simulationusing thereference kitLego,found under with demo videos contained on
Figure 5: Simulation usingreference kitLego.
Turingproved thatfor anyformal systemthere isaTuring machine thatcan be programmed toimitate him. It was thisgenericformal system, with the ability to imitateany otherformal system, which essentiallysought toTuring. Such systemsare calledUniversalTuring Machines. Themathematical logicianAlonzoChurchhas come todefine it: "Any process acceptable to usmenas an algorithmis precisely whataTuring machinecan do."
In April 1936, Turing showedtheir results toJohnVonNeumannat Princeton, when the computersin the modern sense, did not exist.Turingcreatedthe concepts andmathematical foundation, which would benine years afterthe technology usedto materializethe firstelectronic computers, with the participation ofNeumann, ie the transformation of thelogic of theirabstract ideasintoreal engineering. Duringthis time, Turingreturned to Englandandlived onlyideain his mind. The correspondence betweenlogical instructions, the action of the human mindand a machinethat couldbe physicallybuilt, was the final contributionof AlanMathisonTuring.
References:
Turing machinesin Princeton, available at accessed October 2011.
Turing machineswith Stanford,available in accessed October 2011.