[Push] Push complexity

[Maarten]

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-