A Model of Computing

• A Turing machine is a model that consists of a finite state machine, a read/write head, and an infinite tape
• The tape is divided into cells which may contain a symbol from a finite set or be left blank
• The read/write head can travel along the tape one cell at a time
• A Turing machine should have a finite amount of states pulling from a finite set of symbols (called an alphabet)
• A Turing machine will have a start state, and any number of states with no outgoing transmissions, called halting states
• The rules a Turing Machine follows can be written as a transition function, using the letter δ
• A Turing machine can also be depicted as a state transition diagram, which is just a visual representation of a finite state machine
• State transition diagrams and transition functions are equivalent; they can both describe the same thing
• A transition function is written as δ(current state, input symbols) = (next state, output symbol, movement)
• On a state transition diagram, labels are written as input, output, movement (output happens before movement). Changes of state are depicted with arrows that connect states given certain inputs. Movement is separate from changes of state
• Universal Turing machines can read a description of a finite state machine off the same tape as the input data, and then proceed to process it according to this fsm. This makes them similar to interpreters
• A universal Turing machine is a general purpose machine. It can compute anything a real-world computer can compute, and vice versa. This means it defines what is computable, and shows that programs and data are the same thing