If you want to make money online : Register now

[Solved]: Is a language with only a stack of fixed-size integers Turing-complete?

, , No Comments
Problem Detail: 

I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code.

There is only one data type in it (integer, since that's the only data type brainfuck supports). It supports functions and subroutines (to which you can pass integers by value, but not arrays, though you can access an array in the global scope from within a function/subroutine) but it does not support recursion (all function and subroutine calls are inlined). It supports statically allocated arrays (size known at compile time) and has just one unbounded stack. You can store as many items as you like in the stack, unlike with arrays, but you only have one stack for your entire program.

I have these limitations to achieve a balance between ease of use, and fast generated code.

However, I never studied any of this stuff and I actually started this project to learn about compilers (by making one), therefore my question is:

From the above description, is this language turing complete?

Asked By : Cedric Mamo

Answered By : Shaull

If your language supports an arbitrarily large array of integers (even of numbers in $\{0,1\}$), then you can simulate the tape of a TM. Then, clearly your language is Turing complete.

EDIT: based on your comment, you don't have an arbitrary array.

In this case, you can do the following: If you can keep two counters (integers), and increase or decrease them, and check whether they are 0, then you can simulate a two counter machine (Minsky Machine), which is Turing complete (with a caveat).

If you also bound the maximal value that an integer can take, then I believe that your machine is no more powerful than a PDA.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11380

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback