3
$\begingroup$

I am currently studying recursion theory, but I cannot really understand where to put the Primitive Recursive functions in the Chomsky hierarchy.

In my understanding, Primitive Recursive functions contain all finite languages but are not contained in Regular expressions. For instance, I think that $\{a^nb^n | n \in \mathbb{N}\}$ can be computed by a partial recursive function but not by a DFA. But DFA can express the always undefined function, while the primitive recursive function cannot, because they are total.

Am I completely wrong?

$\endgroup$
4
$\begingroup$

The Chomsky hierarchy concerns languages. Languages are total functions from $\Sigma^*$ to $\{0,1\}$, where $\Sigma$ is some non-empty finite set.

A language can be computed by a primitive recursive function if it can be computed by a total Turing machine which has a primitive recursive time upper bound. In particular, every language accepted by an LBA is primitive recursive, since we can simulate an LBA by a deterministic Turing machine running in double exponential time, and $2^{2^n}$ is primitive recursive.

In contrast, it is known that the Ackermann $A(n)$ function is decidable but not primitive recursive. Hence the language $\{ \langle n, A(n) \rangle : n \in \mathbb{N} \}$ is decidable but not primitive recursive.

Consequently, we find that primitive recursive languages sit between Type 0 and Type 1. In other words, every Type 1 language is primitive recursive, and every primitive recursive language is Type 0. Moreover, there are primitive recursive languages which are not Type 1 (for example, any EXPSPACE-complete language), and there are Type 0 languages which are not primitive recursive (for example, the graph of the Ackermann function).

$\endgroup$
  • $\begingroup$ Thank you very much. Can I ask you if the claim that the regular languages are not contained in $PR$ and vice versa, hold?. And if the examples I provided were correct. $\endgroup$ – Briomkez Sep 4 '18 at 16:22
  • 1
    $\begingroup$ Every Type 1 language is primitive recursive, and every primitive recursive language is Type 0. In particular, any regular language is primitive recursive, but there are primitive recursive languages which are not regular. $\endgroup$ – Yuval Filmus Sep 4 '18 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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