Turing Machine

  • General purpose computer
  • Invented by Alan Turing
  • Used to study the limits of what can be computed
  • Components
    • A control unit
      • Simulates a person
    • Read/write head that can read and write symbols on an infinite tape
      • Tape is divided into cells
  • Finite instructions
    • Read from a cell on the tape
    • Write to a cell on the tape
    • Move the tape one cell left
    • Move the tape one cell right

Halting Problem

  • Unsolvable problem of determining whether any program will eventually stop given a particular input

Computer Science Computing Systems