3
$\begingroup$

Is there any computable real number which can not be computed by a higher order primitive recursive algorithm?

For computable real number I mean those that can be computed by a Turing machine to any desired precision in finite time. For higher order primitive recursive algorithm I mean common primitive recursive functions theory extended with first-class functions (as in Ackermann function).

Turing machines are more powerful than higher order primitive recursive functions so there exists the possibility that some computable reals numbers are not expressible by them.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Could you include your preferred definition of "computable real number" and "higher order primitive recursive algorithm"? That will probably make answers more relevant (and also help answerers get some context.) $\endgroup$
    – Caleb Stanford
    Commented May 18, 2017 at 21:55
  • $\begingroup$ Interesting, I've never heard of "higher-order primitive recursion" before. Do you have a link to an authoritative definition? $\endgroup$
    – gardenhead
    Commented May 18, 2017 at 22:46
  • $\begingroup$ @gardenhead Not really. Wikipedia's Ackermann function entry mentions category theory before introducing it. I know it due to Total Functional Programming literature. $\endgroup$
    – user3368561
    Commented May 18, 2017 at 22:59

1 Answer 1

Reset to default
4
$\begingroup$

The set of higher-order primitive recursive reals is essentially the class of functions $\mathbb{N}\rightarrow\mathbb{N}$ which can be represented by a term $\mathrm{Nat}\rightarrow\mathrm{Nat}$ in Gödel's system T.

Since every such function is total, and every well-typed term in the system can be enumerated effectively, there is a relatively easy proof by diagonalization that there is some computable real which cannot be represented.

Improve this answer
$\endgroup$

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.