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?

  • 4
    $\begingroup$ The language of the first paragraph is a bit nonsensical. We usually do not refer to a single machine, or to a single program, as "Turing complete" (or "not Turing complete"). For that, we would need to consider a class of machines, or a class of programs (e.g., a programming language). The main question to answer here is: "given any computable function, is there a machine/program/device in my computation model that computes said function?". If so, the whole computation model (not just a single machine/...) is said to be Turing complete. $\endgroup$
    – chi
    Commented Jun 13, 2023 at 16:10

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.