### I'm giving a guest lecture!

Jan. 6th, 2008 07:07 pm**pmb**

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:

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.