"Who the hell is Alan?"

Cards (16)

  • general models of computation are equivalent (can translate from one model to another)
  • Anything that can be done can be done with a turing machine
  • Turing machines operate on double linked lists
  • Start with the 'input' data on the tape (no reading in from the outside)
  • The ends of the tape are marked by an emptiness/end symbol
  • Turing machine can handle the alphabet defined + a special end symbol. Similar to pushdown automata, use the current state and the value of where the pointer is pointing to determine what to do next. The transition function also handles whether the pointer should be moved left, right, or kept in the same place.
  • i i
  • Turing machines can keep going forever (does not halt)
  • Decideable language = Always halts on a TM, in a rejecting or accepting position
  • Comp. enumerable/ recognisable: Correct words will be accepted by a TM, but incorrect ones may loop forever
  • q0 (start), qyes and qno are special states in the TM
  • eg counting for equal number as bs: bounce end to end replacing with 0s to make pairs. If reach point where eg. looking for a after the last 0 but only find a b - too many bs and not accepting
  • Univerversal TM: a turing machine that can, given a description of a TM and a word, simulate the TM run on the word
  • No TM can decide whether a TM would halt on an e input
  • There are countably many turing machines, but uncoutably many languages, so not all languages are decideable
  • No UTM can tell when if a TM can halt on a given word