[PRL] the simplest universal turing machine

[Dimitris Vardoulakis]

a follow-up discussion
http://scottaaronson.com/blog/?p=284
and an argument about errors in the proof
http://cs.nyu.edu/pipermail/fom/2007-October/012156.html

Dimitris

On 10/26/07, Carl Eastlund <cce at ccs.neu.edu> wrote:
> Yes, the tree structure of the term would be analogous to the tape
> input of the Turing machine.  There has to be an input somewhere.
>
> --Carl
>
> On 10/26/07, Felix S Klock II <pnkfelix at ccs.neu.edu> wrote:
> > Doesn't using the X combinator requires encoding the tree structure
> > of your terms in some manner?
> >
> > I'm not sure that Wolfram's models are easily compared to tree
> > structures terms. . .
> >
> > On Oct 26, 2007, at 7:24 PM, Carl Eastlund wrote:
> >
> > > It always surprises me how worked up the Wolfram Research folks get
> > > over finding new, small, Turing-complete models of computation.  I
> > > always thought they were a dime a dozen.  In any event, if they're
> > > impressed by a 2-state, 3-color Turing machine, someone should show
> > > them the X combinator.
> > >
> > > On 10/26/07, Dimitris Vardoulakis <dimvar at ccs.neu.edu> wrote:
> > >> http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html
> > >>
>
> _______________________________________________
> PRL mailing list
> PRL at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/prl
>