patternModerate
Is a machine Turing-complete when it can decide a context-sensitive language?
Viewed 0 times
cansensitivelanguagecompletedecidecontextwhenmachineturing
Problem
If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete?
Can this be used to prove Turing completeness of a programming language when a program that can decide a string of a context-sensitive language can be written in that programming language?
Or else, can the proof be achieved by using a recursively enumerable language such as the language of prime numbers?
Can this be used to prove Turing completeness of a programming language when a program that can decide a string of a context-sensitive language can be written in that programming language?
Or else, can the proof be achieved by using a recursively enumerable language such as the language of prime numbers?
Solution
No. Context-sensitive languages can be recognized by linear-time nondeterministic Turing machines, which are not Turing complete.
The ability to recognize a recursively enumerable set also does not prove that the programming language is Turing-complete. For instance, the set $\{0,1\}^*$ is recursively enumerable, but is recognizable by a DFA, which is not Turing complete.
Or, consider a programming language with only two constructs: if-then-else statements, and "isprime?()", a primitive function that can be applied to any integer to test whether it is prime. Such a programming language can recognize the language of prime numbers, but is not Turing-complete.
The ability to recognize a recursively enumerable set also does not prove that the programming language is Turing-complete. For instance, the set $\{0,1\}^*$ is recursively enumerable, but is recognizable by a DFA, which is not Turing complete.
Or, consider a programming language with only two constructs: if-then-else statements, and "isprime?()", a primitive function that can be applied to any integer to test whether it is prime. Such a programming language can recognize the language of prime numbers, but is not Turing-complete.
Context
StackExchange Computer Science Q#160653, answer score: 17
Revisions (0)
No revisions yet.