CS 4.5. (ALEVEL) - Model of Computation

Question 1

Turing Machine

Answer 1

• more powerful than FSM because they can utilise a greater range of languages, and because their tape is infinitely long in one direction
  δ(current state, read) = (new state, write, move)
  e.g. δ (S 0 , □) = (S 1 , 1, R)
• definition of what is computable

Question 2

UTM

Answer 2

-capable of representing any FSM
- computes any computable sequence
- Instructions for TM stored on tape
- can be said to act as interpreters
- infinite amount of memory