[Push] Push complexity

[Lee Spector]

Hi Maarten,

You should be able to convince yourself that Push is Turing complete, in
principle, either by considering the non-stack-like
stack-access/manipulation instructions (like PULL and SWAP), or the
arbitrary name/value bindings provided by the NAME type (and SET/GET
functions). Of course you'd also have to remove all of the runtime limits
(providing *unbounded*, not infinite, storage and recursion) -- these are
practical necessities in a GP system, but they're not essential features of
the language per se. By the way, with respect to  non-stack-like stack
manipulation we've added SHOVE (inverse of PULL) in Push2 -- that makes the
Turing completeness more obvious without resorting to the NAME type.

On the Push2 specs: They're now quite settled, and reified in two "nearly
finished" implementations (in Lisp and C++), but not yet written up in one
place. The closest I can provide right now is the Lisp source code, a
recent version of which is at http://hampshire.edu/lspector/temp/push2. But
that's probably not particularly helpful. I am hereby taking your query as
a nudge to draft something better soon -- I'll try to do something
preliminary by the end of the week...

By the way, I think a python implementation would be very cool.

 -Lee



At 7:24 PM +0100 11/10/03, Maarten wrote:
>Hi all,
>
>I was a bit toying with the concepts behind the push language today (this
>instead of finishing that paper for euroGP), and it occured to me that I
>haven't seen a formal proof or indication to what complexity class a push
>program belongs. Does it support arbitrary recursion (with infinite stacks)
>and is thus Turing complete, or does it more properly belong to the class of
>push-down automata? I tried to look into it, but failed to convince myself of
>the Turing completeness of the system. Am I a bit dense, am I missing
>something, maybe the paper that proves this?
>
>On another note, Lee, where can I get a sneak preview at the Push2 specs. I
>might want to try to implement it in python if I find a lost moment
>somewhere.
>
>Just curious,
>
>-Maarten-
>
>
>_______________________________________________
>Push mailing list
>Push at lists.hampshire.edu
>http://lists.hampshire.edu/mailman/listinfo/push

--
Lee Spector
Dean, School of Cognitive Science
Associate Professor of Computer Science    lspector at hampshire.edu
Cognitive Science, Hampshire College       http://hampshire.edu/lspector/
Amherst, MA 01002                          413-559-5352, Fax: 413-559-5438