From Esolang
Jump to navigation Jump to search

Turing Completeness

I don't think it is possible for this to be turing complete, because nested loops aren't implemented --User: Raddish0, 10:06pm April -3rd, 2018

I disagree, the five zeros command gives you the ability to `goto` any location, backward *or* forward (with a negative index) nesting is not required. The problem is that a stack doesn't give you access to all your memory at any time. IIRC extracting a value `N` deep in the stack and putting it on the TOS will give you TC. Rdebath (talk) 05:36, 30 March 2018 (UTC)
It's not Turing-complete, but not for that reason. The issue is that it can only see the current top two stack elements, and the stack elements (being "C integers") have a bounded size. That makes it a push-down automaton. --ais523 11:34, 30 March 2018 (UTC)
Doh, of course "<N> PICK" is only enough for a bounded storage machine with bounded ints. I forgot that for a moment. A PDA seems about right for the existing machine. Rdebath (talk) 19:28, 30 March 2018 (UTC)