Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
