Peter (pmb) wrote,
Peter
pmb

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.
Subscribe

  • (no subject)

    Breaking my LiveJournal silence to note that my officemate of the day the other week was LiveJournal creator bradfitz.

  • See you later, LJ!

    I'm moving everything to just one blog. Too many Russian Spam ads of questionable content lie here. You can follow me at http://imprompt.us for my…

  • Impossible figures

    Rather than ranting about the latest PhD drama (short version: no defense this month, but will defend this summer), I am instead posting about how to…

  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic
  • 17 comments

  • (no subject)

    Breaking my LiveJournal silence to note that my officemate of the day the other week was LiveJournal creator bradfitz.

  • See you later, LJ!

    I'm moving everything to just one blog. Too many Russian Spam ads of questionable content lie here. You can follow me at http://imprompt.us for my…

  • Impossible figures

    Rather than ranting about the latest PhD drama (short version: no defense this month, but will defend this summer), I am instead posting about how to…