Jan. 6th, 2008

pmb: (Default)
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.

Profile

pmb: (Default)
pmb

October 2009

S M T W T F S
    1 23
45678910
11121314151617
18192021222324
25262728293031

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 20th, 2017 07:55 pm
Powered by Dreamwidth Studios