patternMinor
What can't you do without Turing-completeness?
Viewed 0 times
withoutcanyouwhatcompletenessturing
Problem
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?
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?
Solution
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, ...
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, ...
Context
StackExchange Computer Science Q#115229, answer score: 4
Revisions (0)
No revisions yet.