3

I'm writing a joke language that is based on stack operations. I've tried to find the minimum amount of instructions necessary to make it Turing complete, but have no idea if a language based on one stack can even be Turing complete. Will these instructions be enough?

IF (top of stack is non-zero)
WHILE (top of stack is non-zero)
PUSH [n-bit integer (where n is a natural number)]
POP
SWAP (top two values)
DUPLICATE (top value)
PLUS (adds top two values, pops them, and pushes result)

I've looked at several questions and answers (like this one and this one) and believe that the above instructions are sufficient. Am I correct? Or do I need something else like function calls, or variables, or another stack?

If those instructions are sufficient, are any of them superfluous?

EDIT: By adding the ROTATE command (changes the top three values of the stack from A B C to B C A) and eliminating the DUPLICATE, PLUS, and SWAP commands it is possible to implement a 3 character version of the Rule 110 cellular automaton. Is this sufficient to prove Turing completeness?

If there is an example of a Turing complete one-stack language without variables or functions that would be great.

theEpsilon
  • 1,800
  • 17
  • 30
  • Read this: https://math.stackexchange.com/questions/112011/how-to-prove-a-programming-language-is-turing-complete – Stephen C Jul 02 '17 at 00:55
  • What does the `WHILE` instruction do? Execute the following instruction until the top of the stack is zero? – RBarryYoung Jul 06 '17 at 18:54
  • @RBarryYoung I didn't really think about that. It would probably execute a code block directly following it, a block which can have multiple instructions – theEpsilon Jul 07 '17 at 04:17
  • "A block of instructions" for `IF` and `WHILE` is inherently a second stack then, especially if they can be nested. I assumed that this was more like a machine language where only a single following instruction can be conditionalized/repeated. The difference is important because a Block is like a local anonymous subroutine, and since you are already using one stack for global data state, you would need a second stack to know where to resume to in the calling context. – RBarryYoung Jul 07 '17 at 13:27
  • Hmm, the Instruction Stack would only have to be as big as the deepest nesting of the program though, and without abstraction/recursion that's inherently limited to less than the length of the program. Not sure if that could be just a closed/limited stack then (as opposed to a second open/unlimited stack). – RBarryYoung Jul 07 '17 at 13:58

3 Answers3

4

If you want to prove that your language is Turing complete, then you should look at this Q&A on the Math StackExchange site.

One approach is to see if you can write a program using your language that can simulate an arbitrary Turing Machine. If you can, that is a proof of Turing completeness.

If you want to know if any of those instructions are superfluous, see if you can simplify your TM emulator to not use one of the instructions.

But if you want to know if a smaller Turing complete language is possible, look at SKI Combinator Calculus. Arguably, there are three instructions: the S, K and I combinators. And I is apparently redundant.

svick
  • 236,525
  • 50
  • 385
  • 514
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • Thanks for that link. I've been thinking about how I might implement a Turing machine in the instructions in my question. I'm certain that I could do it with two stacks, but since I can't recover the values popped off the top I don't know if it's possible – theEpsilon Jul 02 '17 at 01:28
  • Answer - no it is not sufficient. For a proof, you need to demonstrate that you can implement any Turing machine. (Within practical constraints of space and memory, of course.) Or more broadly, that you can perform any computation that can be expressed using a Turing machine ... which is more difficult. Or that your language is equivalent to some other Turing-complete language. – Stephen C Jul 02 '17 at 02:47
3

A language based only on a single stack can't be Turing complete (unless you "cheat" by allowing stuff like temporary variables or access to values "deeper" in the stack than the top item). Such a language is, as I understand it, equivalent to a Pushdown Automata, which can implement some stuff (e.g. context-free grammars) but certainly not as much as a full Turing machine.

With that said, Turing machines are actually a much lower bar than you'd intuitively expect - as originally formulated, they were little more than a linked list, the ability to read and modify the linked list, and branching. You don't even need to add all that much to a purely stack-oriented language to make it equivalent to a Turing machine - a second stack will technically do it (although I certainly wouldn't want to program against it), as would a linked list or queue.

Correct me if I'm wrong, but I'd think that establishing that you can read from and write to memory, can do branching, and have at least one of those data structures (two stacks, one queue, one linked list, or the equivalent) would be adequate to establish Turing completeness.

Take a look, too, at nested stack automata.

You may also want to look at the Chomsky hierarchy (it seems like you may be floating somewhere in the vicinity of a Type 1 or a Type 2 language).

EJoshuaS - Stand with Ukraine
  • 11,977
  • 56
  • 49
  • 78
2

As others have pointed, if you can simulate any Turing machine, then your language is Turing-complete.

Yet Turing machines, despite their conceptual simplicity and their amenity to mathematical treatment, are not the easiest machines to simulate.

As a shortcut, you can simulate some simple language that has already been proved Turing-complete.

My intuition tells me that a functional language, particularly LISP, might be a good choice. This SO Q&A has pointers to what a minimum Turing-complete LISP looks like.

Apalala
  • 9,017
  • 3
  • 30
  • 48