4 ms·

> I think this language is just shy of being Turing complete. It's probably in the same class as regular expressions. If it is possible to code an infinite loo

> I think this language is just shy of being Turing complete. It's probably in the same class as regular expressions. If it is possible to code an infinite loop, that tends to be enough to bring a language up to the level of being Turing equivalent. To put it more strongly, it is really hard to define a nontrivial language that has infinite loops that is not Turing equivalent. And in fact I can see how to simulate a cpu in this language, so there you go.

xigency 11y ago
Not so. Without the ability to implement or simulate a stack, a language cannot be Turing complete. Otherwise, that limits the computational power to that of a finite-state machine. Even so, being able to implement a stack is not sufficient, because pushdown automata are defined as finite-state machines combined with a stack, and PDA's are a proper subset of Turing-complete languages. Given that a CPU in this case could be stateless or have a limited number of states, that does not change the class of language. Anyway, I see the author has implemented arrays now, and more specifically dynamically-sized arrays, so I will concede that it is Turing complete. That wasn't really the intent of my post, as there are other ways to devise a language, but cool none the less. For a view of the classes of languages in computation, see this hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarch... Here, the set of languages that Turing machines recognize are labeled as recursively enumerable languages.
- DougMerritt 11y ago
  Thank you, but I am aware of all that, and I asked for arrays above in part to be able to emulate a stack (or a tape, if going the turing machine route). (I could emulate a bounded stack with a bunch of variables and conditionals choosing them, but that's pretty ugly, and brings home just how bounded the result would be) > CPU in this case could be stateless or have a limited number of states The bounded state is an issue, but it is for Pentiums as well. We have approximations of Turing equivalent machines in real life, and that's close enough. Regarding these other things: > pushdown automata are defined as finite-state machines combined with a stack I didn't say it was impossible, I said it was difficult with a nontrivial language -- because I've seen people try, and accidentally make things Turing equivalent. If you know what you're doing, like you for instance, then sure, you just leave out problematic features and make sure you don't leave the level of the Chomsky hierarchy you were aiming for. But no, people always want handy things like assignment and arithmetic expressions and loops and function calls and so on. :) A classic example is pure standard SQL (up to a few years ago), which had no loop construct, and the language was famously sub-Turing. But if the embedding language puts some SQL in a loop, it's trivial to emulate a CPU with simple SQL, which won't surprise someone classically trained like yourself, but does tend to surprise random programmers in the wild. (I hear a more recent SQL standard added loops, which I have mixed feelings about.)

xigency 11y ago

Not so. Without the ability to implement or simulate a stack, a language cannot be Turing complete. Otherwise, that limits the computational power to that of a finite-state machine. Even so, being able to implement a stack is not sufficient, because pushdown automata are defined as finite-state machines combined with a stack, and PDA's are a proper subset of Turing-complete languages. Given that a CPU in this case could be stateless or have a limited number of states, that does not change the class of language. Anyway, I see the author has implemented arrays now, and more specifically dynamically-sized arrays, so I will concede that it is Turing complete. That wasn't really the intent of my post, as there are other ways to devise a language, but cool none the less. For a view of the classes of languages in computation, see this hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarch... Here, the set of languages that Turing machines recognize are labeled as recursively enumerable languages.

DougMerritt 11y ago
Thank you, but I am aware of all that, and I asked for arrays above in part to be able to emulate a stack (or a tape, if going the turing machine route). (I could emulate a bounded stack with a bunch of variables and conditionals choosing them, but that's pretty ugly, and brings home just how bounded the result would be) > CPU in this case could be stateless or have a limited number of states The bounded state is an issue, but it is for Pentiums as well. We have approximations of Turing equivalent machines in real life, and that's close enough. Regarding these other things: > pushdown automata are defined as finite-state machines combined with a stack I didn't say it was impossible, I said it was difficult with a nontrivial language -- because I've seen people try, and accidentally make things Turing equivalent. If you know what you're doing, like you for instance, then sure, you just leave out problematic features and make sure you don't leave the level of the Chomsky hierarchy you were aiming for. But no, people always want handy things like assignment and arithmetic expressions and loops and function calls and so on. :) A classic example is pure standard SQL (up to a few years ago), which had no loop construct, and the language was famously sub-Turing. But if the embedding language puts some SQL in a loop, it's trivial to emulate a CPU with simple SQL, which won't surprise someone classically trained like yourself, but does tend to surprise random programmers in the wild. (I hear a more recent SQL standard added loops, which I have mixed feelings about.)