I'm giving a guest lecture!
I'm giving a guest lecture on computation and computability and the halting problem! It was impossible to find a good drawing of a Turing machine on the Internet - even on the HMC CS department web pages - so I had to make my own:
Fig. 1 A Turing machine, with an eye to read the
tape, a pencil with an eraser to mark and erase, a state
machine in its belly, a unicycle to move it back and
forth, and a lightbulb to indicate that it's done.
This bizarre machine can compute anything that is computable (if the Church-Turing thesis holds), and can, if provoked, simulate a von Neumann architecture with only a polynomial slowdown. If you ever need to talk about Turing machines, please feel free to steal the image.
Fig. 1 A Turing machine, with an eye to read the
tape, a pencil with an eraser to mark and erase, a state
machine in its belly, a unicycle to move it back and
forth, and a lightbulb to indicate that it's done.
This bizarre machine can compute anything that is computable (if the Church-Turing thesis holds), and can, if provoked, simulate a von Neumann architecture with only a polynomial slowdown. If you ever need to talk about Turing machines, please feel free to steal the image.