The set of real numbers contains element which can be represented (there exists a way to write them down on paper). These numbers include:

  • Integer numbers, such as $-8$, $20$, $32412651$
  • Rational numbers, such as $\frac{7}{41}$, $-\frac{14}{3}$
  • Algebraic numbers
  • Any other number that can be created by a chain of functions whose definition is also finite (ex.: $\sin(\cos(\sqrt{445}))$, $\pi$, $e$)

Another way of thinking about these is that it's possible to write a computer program occupying a finite amount of space that can generate them to any precision (or return it's nth digit).

The set of reals also contains numbers which are impossible to represents (whose digits follow absolutely no logic). We never use such numbers because there is no way of writing them down.

My questions are:

  • What are these numbers called?
  • What is a more formal definition of them?
  • 2
    $\begingroup$ I've heard them called non-computable numbers. $\endgroup$ – Paddling Ghost Sep 5 '15 at 3:57
  • $\begingroup$ Try this: en.wikipedia.org/wiki/Definable_real_number $\endgroup$ – Alan Sep 5 '15 at 4:49
  • 1
    $\begingroup$ Intresting(?) fact: almost all real numbers are not computable. $\endgroup$ – skyking Sep 5 '15 at 9:36

The numbers you are describe in your list are called computable numbers meaning they can be computed to arbitrary precision. Equivalently, a number $x$ is computable if it is decidable, given rational $a$ and $b$, if $x\in (a,b)$.

The other numbers are said to be noncomputable. It is worth noting, however, that some noncomputable numbers can still be written down - for instance: $$\sum_{n=0}^{\infty}2^{-BB(n)}$$ where $BB$ is the busy beaver function (which isn't computable).

  • 2
    $\begingroup$ Pretty sure they are looking for the definable numbers, which include the computable but also others that can be written down but not computed: en.wikipedia.org/wiki/Definable_real_number $\endgroup$ – Alan Sep 5 '15 at 4:49
  • 1
    $\begingroup$ @Alan What do they mean with "standard model" of set theory? As they list $0^{\#}$ as a definable number, $L$ is not what they're having in mind (and it probably should read that $0^{\#}$ is definable if it exists anyways). $\endgroup$ – Stefan Mesken Sep 5 '15 at 7:53
  • 1
    $\begingroup$ @Alan: That page should be deleted from Wikipedia. Or at least rewritten from scratch. $\endgroup$ – Asaf Karagila Sep 5 '15 at 9:16

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.