From Esolang
Jump to navigation Jump to search

Is this really Turing-complete? If numbers on the stack are bounded, I think it would be pretty easy to implement it as a push-down automaton. If they are not, I'm guessing the % instruction might make it more powerful, though I'm not sure how much, since I don't think information can be extracted from the third cell without destroying some information from the first two. -- Koen (talk) 15:24, 3 October 2012 (UTC)

Agree, can't see it being Turing-complete as it is. The language is irritatingly badly defined but what sense I can make of it is that the values on stack are one-character long (8 bits). --Keymaker (talk) 16:42, 3 October 2012 (UTC)
Assuming sequences can be used recursively, you also have the call stack. This has been used effectively for TC-ness before: e.g. Underload ~:!()^ fragment, or for that matter Forth itself. --Ørjan (talk) 23:39, 3 October 2012 (UTC)
You can call previously defined sequences like:
:a++++; :baa; bbbb+.
prints '!' (dec 33) but
++++++++ ++++++++ ++++++++ ++++++++ :b + :a.; ; b a
just crashes the interpreter if you try to define a sequence inside another sequence definition. I don't know if this is enough. --Keymaker (talk) 09:45, 4 October 2012 (UTC)
You don't need to define a sequence inside another, it is enough for one sequence to be able to call itself recursively (inside loops, naturally.)
Ignoring the implementation's tiny stack limits, what worries me more is that [ is utterly broken - it skips to the next ], not the matching one. --Ørjan (talk) 16:25, 4 October 2012 (UTC)
To summarize: Between the specification's ambiguity, and the implementation's tiny limits and at least one obvious bug, I believe there is a compromise that is a genuinely TC language, even while keeping the byte sized values. --Ørjan (talk) 17:12, 4 October 2012 (UTC)
And I would be really surprised if the % code isn't undefined behavior. --Ørjan (talk) 19:36, 4 October 2012 (UTC)
If the cells were unbounded, could 3 cell Brainfuck be used for turing completeness? I'd imagine so. Push, pop, and swap could use the current value and the top two values of the stack as three cells. The problem is this enough control to translate Collatz functions? Camto 03:28, 10 March 2019 (UTC)