Talk:Staq

Turing-completeness based on "tape size"?

Is that Turing-completeness proof giving a tape of length 256, or with 256 possible values? If the tape is only finitely long, you haven't proved TCness after all. --ais523 11:55, 28 June 2011 (UTC)

The potential proof concerns a tape of length 256, but with unbounded possible values. This would make it a Minsky machine, which is Turing-complete. —Maharba 17:28, 28 June 2011 (UTC)

Aha. I'll go clarify that in the article. --ais523 22:21, 28 June 2011 (UTC)

Just to be completely clear, it would require an infinite amount of time to construct an infinitely long tape using the code I provided; the tape is just a stack and the number of values on the stack is preset, created one at a time. (On a side note, I'm fairly sure it'd be possible to do some adjusting that would allow the tape size to be arbitrary, creating a new cell whenever a > or < brings the pointer out of the existing bounds. I'll try and work more with idea this later.) Although the interpreter limits values to 16-bit unsigned ints, that's not a limitation of the language itself. And beyond this, the Stack page says that a language with two stacks and sufficient access to both should be Turing complete, and I'm fairly certain this meets that criteria. - Madk 00:03, 29 June 2011 (UTC)

It's not necessary to make a "tape size", as there are two (apparently unbounded) stacks, which makes this turing complete. This header:

   {>|n?xtx|} {<n?xtx} {+i} {-d} {,`} {.;} &|&

prefixed to any Brainfuck program gives a valid Staq program that does the same thing as the Brainfuck program. It works by having > and < create new space on the stacks automatically: n?x gives an extra 0 if the stack is empty. --Marinus 20:42, 4 July 2011 (UTC)