5
$\begingroup$

We've developed an esoteric language. In this language, a program contains a static amount of code, and a static amount of storage space. However, parts of the program can recurse, so the interpreter will spawn another copy of a subset of the code and additional storage space to match. Can this language be Turing Complete?

$\endgroup$
  • $\begingroup$ Possible duplicates. $\endgroup$ – Raphael Jun 9 '15 at 18:08
  • $\begingroup$ I do not see why storage should be an issue. A single integer can store an arbitrary Turing Machine configuration (tape and head position), and a finite state transducer can change such a configuration into the next one obtainable by application of a transition. And that can be repeated with a loop. Is that really the question you want to ask? $\endgroup$ – babou Jun 9 '15 at 20:41
  • 2
    $\begingroup$ @babou limited storage implies limited integer range. if my integers only go up to 255 then there are a lot of turing machine configurations that I can't store. $\endgroup$ – Sparr Jun 9 '15 at 20:44
  • 1
    $\begingroup$ It might be useful to describe some of the features in more detail: in particular, can the program inspect it's own stack? If not, then it seems that each function call only has access to a finite amount of information, which would imply turing-incompleteness. But we need a bit more info to be sure. $\endgroup$ – cody Jun 9 '15 at 22:27
  • $\begingroup$ Your point is well made. But I wanted to be sure. My only worry was whether you allowed encodings or not. Your answer is much stronger and forces me to change my view of the problem, since it also prevent storing pointers. $\endgroup$ – babou Jun 9 '15 at 22:35
7
$\begingroup$

Given your very strict interpretation of limited memory size, limiting also the size of integers, one consequence is that it is not possible to play encoding games with integers (such as Gödel enumerations or encodings).

Another consequence is that you cannot have a way of retrieving the address of a memory location in order to make pointers. The reason is that unbounded recursion implies that memory addresses will have unbounded size (which is a bit inconsistent on the implementation side, but I guess I have to ignore it). If there was an instruction to retrieve the address of a variable, the space needed to store this address could well exceed all of the memory available for a given recursive call. Hence there is no hope of manipulating addresses.

Hence, each recursive call can only access a finite amount of information, say $n$ bits, which may be seen also a one of $2^n$ symbols. There is as much information, i.e. one of those symbols, memorized for each of the previous calls, but not accessible on the recursion stack.

Of course a little bit of information is passed as parameter at each recursive call, and some is returned when it terminates.

So all this pretty well describes a pushdown automaton.

Hence all you can do is recognize or generate context-free languages, or some equivalent computation. You are pretty far from Turing completeness.

But if your model allowed storing pointers to local variables, then, even without Gödel encodings in integers, you could have Turing completeness.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.