[FoRK] minimal universal turing machine

Rohit Khare <khare at alumni.caltech.edu> on Fri Oct 26 10:51:56 PDT 2007

Ben Sittler: also did you see that the minimal universal turing  
machine has (apparently) been proven?
Rohit Khare: huh?
Ben Sittler: apparently a two-state three-color machine is the  
minimal one capable of universal computation
Ben Sittler: stephen wolfram set a bounty on proving or disproving it  
earlier this year, and somebody did prove it
Ben Sittler: http://blog.wolfram.com/2007/10/ 
the_prize_is_won_the_simplest.html
Ben Sittler: i foolishly spent a few minutes last night hacking  
together a simulator: http://zoehep.xent.com/~bsittler/t23.html
Rohit Khare: don't tell me you're using tables?!
Ben Sittler: yep :)
Rohit Khare: sick, sick man...
Ben Sittler: works like a charm
Ben Sittler: i insert new cells with rowspan=# of rows - 1 to grow  
the tape
Ben Sittler: otherwise i would use divs and br
Ben Sittler: which are way faster but do not give the nice layout

More information about the FoRK mailing list