From Esolang
Jump to navigation Jump to search

I think this is Turing-complete even with finitely long programs. It should be possible to use a and b as a Minsky machine of sorts; although this is complicated by the need to also use them to manipulate the IP, I think it's possible to get away with doing that on the times that b is zero (using a to store all the data by multiplying together primes). --ais523 15:18, 9 October 2008 (UTC)

As implemented, a and b are not unbounded. As described, they may be. --Quintopia 21:00, 11 December 2008 (UTC)

Just about any language is Turing-complete if infinite programs are allowed. (If the infinite program isn't required to be given constructively, the language can be considered more powerful than a Turing machine: just feed in a program which is an infinitely long if..then..else chain that tests every possible input, outputting "yes" for the inputs that represent Turing machines that halt and "no" for those that don't, and your language can solve the Halting Problem.) So I'm not sure it makes sense to mention that condition specifically. --Chris Pressey 22:10, 13 December 2010 (UTC)
I'm a little wary of the Minsky machine reduction, at least the approach ais523 has described. Performing a jump requires a clear b register, which requires that you multiply values together, which (since the language only supports increment) requires a loop, which requires a jump.
But you might be able to make up for this shortcoming with indirection. Maybe? Possibly not. Possibly you could if the cell referenced indirectly was modulo some constant. Otherwise, if the register can take on any value, you'd have to sprinkle the addresses of jump targets in infinitely many places in the program. Chris Pressey (talk) 17:38, 18 October 2012 (UTC)
Um wait. You can say =Ab and store b somewhere in the program. The article says that each cell can hold any integer value. So it's not like we're restricted to two registers here, we could have a large (finite) number. Should be no problem getting a Minsky machine out of that with some judicious swapping at points. Chris Pressey (talk) 19:03, 18 October 2012 (UTC)