Are all computing languages restricted to primitive recursive functions capable of modeling each other?

399 Views Asked by At

Is there a universal language restricted to the primitive recursive functions - without while loops or goto etc - that can effectively model all other languages similarly so restricted?

Is there something analogous to the notion of Turing Complete, but for languages restricted to primitive recursive functions?

To be clear, I'm only talking about languages that do not allow total functions which are not primitive recursive functions.

I think this is similar to this question, but for PR instead of allowing total functions.

1

There are 1 best solutions below

2
On

No, there is no such language

There is a nice proof by contradiction here. Let $f_n$ be the nth primitively recursive function (under some ordering, like alphabetical BlooP programs). Now define $$f(n)=f_n(n)+1$$ $f$ isn't a primitively recursive function because it's value differs from $f_n$ at $f(n)$.

Now suppose there is a primitively recursive language that could model other primitively recursive languages. It would be able to calculate the value of $f(n)$ by simulating the nth primitively recursive program*. But we know $f$ isn't primitively recursive so the language can't be primitively recursive.

*Primitively recursive languages have bounded loops this means they all halt. The halting problem prevents us from using this construction on Turing Machines.