HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is a machine Turing-complete when it can decide a context-sensitive language?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#160653, answer score: 17

Revisions (0)

No revisions yet.