Studied by 0 people
Looks like no one added any tags here yet for you.
Components of a Turing Machine
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
How a Turing machine works
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
