3
$\begingroup$

I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose.

I also know that some non-Turing-complete languages can't use unbounded loops, and I suppose that making unbounded loops forbidden is enough to make a language non-Turing-complete. But it doesn't mean that it's the only way.

So, in general, what common properties or abilities of general purpose languages are only possible with a Turing-complete language?

If I decide to design a non-Turing-complete language, what common purpose functions won't I be able to implement with it? Which common source code structures should I forbid?

$\endgroup$
  • $\begingroup$ Giving a Turing machine, finine amount of tape/memory makes it non-Turing complete. $\endgroup$ – RandomPerfectHashFunction Sep 29 at 20:17
2
$\begingroup$

Real world computers are not Turing complete (they have a finite amount of memory) and are equiparable to Linear Bounded Automata.

So the easiest way to design a non-Turing-complete language is to design a language that has only a limited amount of memory (the memory can also be a function of the input length) and don't worry about other restrictions.

But as soon as you allow some kind of unboundness it's not an easy task to avoid Turing completeness, for example two variables that can store an arbitratrily large integer, a JUMP operator, an IF condition and a + operator already defines a Turing complete language (Counter mmachines).

It's curious that even some games (Chess, Magic The Gathering, Minecraft, ...) if you allow level/boards of unbounded size.

The common way is to use bounded loops or bounded recursion; you can take a look to some real-world non Turing-complete languages: SQL, data languages (e.g. Regular expressions,HTML,...), LOOP language, Charity, ...

$\endgroup$
  • $\begingroup$ Restricting a Turing machine's access to memory also makes it non-Turing complete. For example, restricting a Turing machine to access only the last k recently used memory cells. (k<number of memory cells) $\endgroup$ – RandomPerfectHashFunction Sep 29 at 20:29
  • 1
    $\begingroup$ @RandomPerfectHashFunction: yes! Also if you bound the number of reversals. $\endgroup$ – Vor Sep 29 at 20:37
2
$\begingroup$

As an example where unbounded loops are needed: I can write an emulator for any machine, running in a loop. With unbounded loops, that emulator can run forever. With bounded loops, I must calculate beforehand how long that emulator runs. That calculation might return "the simulator will run for one trillion trillion trillion years", which in theory makes a huge difference, but in practice not.

But mostly questions about Turing completeness are asked in a context like "Postscript is Turing complete", "A C++ compiler is Turing complete", "Conway's Game of Life is Turing complete", where the question isn't so much about primitive recursive vs. non-primitive recursive, but whether we can run useful programs at all.

$\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.