SLR 9

Turing Machines

Components: 

• Infinitely long tape 

• Finite alphabet 

• Read/write head 

• Set of rules 

• Finite set of states 

Transition Rules: 

δ (current state, input symbol) = (new state, output symbol, movement) 

• Change value where the read write head is first – move last 

δ (S0,0) = (S3,1,<-) 

• Start on state 0, with an input of 0 

• State changes to 3, input is 1, and movement is to the left 

Universal Turing Machine: 

• Can theoretically represent any computation 

• An interpreter which reads the description of any arbitrary Turing Machine (M) and faithfully executes operations on data precisely as M does 

• Predecessor to a computer 

• formal model of computation 

• contains a read-write head, finite state machine, and an infinitely long tape

• can be viewed as a computer which runs a single program - like a finite state machine

• the finite state machine will have a start state, and may have a number of states from which there are no transitions - halting states

• stop after reaching a halting state - can be entered at any time in the execution of its input data

• tape is divided into cells, each of which can be blank or contain a symbol

• set of symbols is called an alphabet and must be finite