0
$\begingroup$

On a turing machine and in the lambda calculus one can define transcendental numbers such as Pi, the golden ratio, etc. These are computatible functions with 0-arity that never terminate. In the theory of general recursive functions (which also defines the same class of functions as turing machines and lambda calculus) the output is always a natural number N, or undefined. How does one define transcendental numbers in the theory of general recursive functions (mathematical functions defined by Gödel)

$\endgroup$

1 Answer 1

4
$\begingroup$

If you are only interested in transcendental (or at least only irrational) numbers, you can safely identify the number $x$ with the function $d_x : \mathbb{N} \to \mathbb{N}$ that on input $n$ outputs the $n$-th digit of the decimal expansion of $x$.

If you want all real numbers, that does not lead to a satisfactory theory of computation. A suitable way to handle reals there is to let a function $f : \mathbb{N} \to \mathbb{N}$ code a real number $x$ if $$\forall n \in \mathbb{N} \ |\nu(f(n)) - x| < 2^{-n}$$ where $\nu : \mathbb{N} \to \mathbb{Q}$ is some standard bijection. This means that there are many functions coding the same real, but that is unavoidable.

$\endgroup$
2
  • $\begingroup$ I understand that its not possible to define ALL reals [uncountable], and your answer really hits it on the head for me - Thank you. $\endgroup$
    – RFV
    Oct 10, 2022 at 17:02
  • $\begingroup$ @RFV Thanks for pointing that out, I hadn't updated my profile in years. $\endgroup$
    – Arno
    Oct 10, 2022 at 17:07

Your Answer

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

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