Talk:Piet

Sketch of TC proof

For the computational class, I have this idea but I don't know how to continue as there are some holes in my knowledge on the subject. Would someone please complete it?

The language specification does not specify a size for the stack elements, so they may be arbitrary-size integers (the author even seems to assume that in his Fibonacci program since it prints the first 100 numbers from the Fibonacci sequence, but the 100th Fibonacci number even exceeds 64 bits).

The stack rotate operator gives access to any stack position at a given time, thus making the stack equivalent to a register bank. I recently read a claim that 5 unlimited-size registers should be enough for TC.

I think that that could be sufficient as to prove that Piet is Turing-complete. Not very formal, admittedly. --pgimeno 23:28, 10 Jun 2005 (GMT)

As long as you can code a FSA in the rest of Piet it sounds pretty good to me. (And actually, I'm OK with informal sketches of proofs; they're easier to read, for one thing. As long as it's fairly persuasive, filling in the details can be left as an exercise)

OK, I just added an article on Minsky machines, which might be useful to reference in proofs like this. --Chris Pressey 02:29, 11 Jun 2005 (GMT)

Thank you, that's exactly what I neeeded. I'm adding an explanation now. --pgimeno 10:30, 11 Jun 2005 (GMT)

I think that even with limited integer size (but unlimited stack) the rotate operation can make the language powerful enough as to make it TC. --pgimeno 11:42, 11 Jun 2005 (GMT)

I think so too, though I have no formal proof. --Rune 11:52, 11 Jun 2005 (GMT)

Hm, I have to take back that claim. If the integer size is limited, then the rotate operation needs a limited integer as an argument, thus the whole stack is not accessible at random anymore. My guess is that limited integer size and unlimited stack converts Piet in a push-down automaton. --pgimeno 18:41, 14 Jun 2005 (GMT)

You are right. I completely ignored the fact that the rotate function's argument is taken off the stack. --Rune 22:18, 14 Jun 2005 (GMT)

Other way to prove TC: translate brainfuck to piet

I think this article is worth mentioning: http://mamememo.blogspot.co.uk/2009/10/piet-is-turing-complete.html --(this comment by 31.205.75.235 at 21:30, 31 October 2012‎ UTC; please sign your comments with ~~~~)

Roll

I think I got the whole "roll" thing right but I'm not sure. If I didn't, please change it! NotVeryGoodAtThis (talk) 19:00, 11 June 2020 (UTC)