# Talk:Staq

Jump to navigation
Jump to search

## 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)

- Aha. I'll go clarify that in the article. --ais523 22:21, 28 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)