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)
1 Answer
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.
-
$\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$– RFVOct 10, 2022 at 17:02
-
$\begingroup$ @RFV Thanks for pointing that out, I hadn't updated my profile in years. $\endgroup$– ArnoOct 10, 2022 at 17:07