pmb: (Default)
[personal profile] 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:


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.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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 Jun. 23rd, 2017 07:00 pm
Powered by Dreamwidth Studios