[PRL] the simplest universal turing machine
Carl Eastlund
cce at ccs.neu.edu
Fri Oct 26 22:01:05 EDT 2007
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
> >>
More information about the PRL
mailing list