[PRL] the simplest universal turing machine
Peter R. Douglass
peterd at ccs.neu.edu
Fri Oct 26 20:58:20 EDT 2007
Use the P and A combinators, and you eliminate the tree structure.
--PeterD
Felix S Klock II 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
>>>
>>>
>> --
>> Carl Eastlund
>>
>> _______________________________________________
>> PRL mailing list
>> PRL at lists.ccs.neu.edu
>> https://lists.ccs.neu.edu/bin/listinfo/prl
>>
>
>
> _______________________________________________
> PRL mailing list
> PRL at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/prl
>
More information about the PRL
mailing list