Suppose that we have a computer program, my question is whether a human can type in any real number - say in $[0,10]$ - that she would like to type in a finite amount of time? Suppose that the program allows typing in any basic expressions like sum, multiplication, square-root, limits etc.

in a more formal way: Choose one real number $x\in [0,10]$, is it possible to express $x$ in a way that a computer can understand*?

*can understand = if $y$ is another such number, computer can tell whether $x>y, y>x$ or $x=y$.

EDIT: For example, square-root 2 can be typed as $\sqrt{2}$ and that is okay. As asked in comments, computer does not have an infinite memory, What is imporant is that the program can distinguish any two numbers that are typed in. For example, even though it is not possible to represent $\sqrt{2}$ in a computer, it can understand that $\sqrt{3}$ is bigger than $\sqrt{2}$.

  • Nope, they have infinite decimals. – Zelos Malum Nov 8 '15 at 19:08
  • You mean like 0.88888888 in definitely? – Nonlinear Nov 8 '15 at 19:10
  • that, squareroot of 2, any real number has infinitely many decimals so they cannot be written out by computers ever. – Zelos Malum Nov 8 '15 at 19:11
  • @Zelos Malum: Yes but the square-root of $2$ can be typed as the square-root of $2$. – nombre Nov 8 '15 at 19:12
  • 1
    "That she would like to type" is a possible loophole. The human has a finite brain, and therefore can't think of more than finitely many numbers. – Robert Israel Nov 8 '15 at 19:35
up vote 6 down vote accepted

When you have finite or countable many symbols:

No, when you only allow symbols from a finite (or countable) set of possible symbols like $\lim$, $\sqrt{}$, digits and so on, the set of all possible terms (with finte length) someone can type is countable. But there are uncountable many reals in $[0,10]$. Thus there are reals which are "untypable"...

This is related to definable numbers: There are only countable many expressions to define a number in first order logic but there are uncountable many reals -> There are undefinable numbers. See also the answers and comments to the question Is there an example for an undefinable number? for examples of undefinable/uncomputable numbers.

When you have uncountable many symbols:

Then you can assign to each real number a different symbol which stands for it (like the symbol "$\pi$" stands for the number $\pi$) and voila: Every real can be typed by using its symbol ;-)

(Let's assume that the continuum hypothesis is true as a axiom for this answer: There is no uncountable set with cardinality less then the cardinality of $\mathbb R$)

Update: There are computable numbers $x$ for which you cannot decide whether $x=0$ or $x > 0$. To cite a comment of Robert Israel to this answer:

Consider a predicate $S(n)$ that can be computed for each natural number $n$. Define $x=\sum_{n=1}^\infty 2^{−n}d(n)$, where $d(n)=1$ if $S(n)$ is true and 0 otherwise. Since each $S(n)$ can be computed, $x$ is computable in the sense that arbitrarily good rational approximations of $x$ can be computed. Now it might be that all $S(n)$ happen to be false, but there is no proof (in your favourite consistent formal system) of this fact. Then it is impossible to decide (in that system) whether $x=0$ [or $x > 0$].

  • and if an uncountable set of characters is allowed, you can type any real number using single character – z100 Nov 8 '15 at 19:21
  • @z100: You are right! I add your comment to my answer... – Stephan Kulla Nov 8 '15 at 19:24
  • @z100: But I guess we need the continuum hypothesis as an axiom so that there is no uncountable set of symbols with cardinality less then the cardinality of $\mathbb R$ ;-) – Stephan Kulla Nov 8 '15 at 19:31
  • @tampis I did not mean to write every real number down, then you are right there are uncountable of them. I am wondering if there is a reference / paper about the issue you raise, best. – Nonlinear Nov 8 '15 at 19:52
  • 1
    Consider a predicate $S(n)$ that can be computed for each natural number $n$. Define $x = \sum_{n=1}^\infty 2^{-n} d(n)$, where $d(n) = 1$ if $S(n)$ is true and $0$ otherwise. Since each $S(n)$ can be computed, $x$ is computable in the sense that arbitrarily good rational approximations of $x$ can be computed. Now it might be that all $S(n)$ happen to be false, but there is no proof (in your favourite consistent formal system) of this fact. Then it is impossible to decide (in that system) whether $x = 0$. – Robert Israel Nov 8 '15 at 21:54

Any real number $\xi$ you, or a more experienced mathematician, can think of can be defined and described in terms of text and universally accepted formulas, whence: be expressed in TeX-code on less than two ASCI-pages or so. Any computer will accept this as input. Such an input determines $\xi$ as an element of ${\mathbb R}$ once and for all, in other words: to any desired number of decimal places. Of course it may be the case that your pocket calculator will not be sufficient to compute these digits one after the other.

  • is there a reference that you know about this result? – Nonlinear Nov 8 '15 at 19:34
  • 1
    I think this answer is wrong. See the wikipedia article "Computable number": There are numbers a computer can never calculate (see the article computability for more details). There are also undefinable numbers... There are only countable many possible TeX-articles. How do you want to define with them each of the uncountable many real numbers?! ;-) – Stephan Kulla Nov 8 '15 at 19:41
  • Can you "think of" an undefinable number? – Robert Israel Nov 8 '15 at 19:47
  • @RobertIsrael very interesting point! – Nonlinear Nov 8 '15 at 19:56
  • @RobertIsrael -- I,too, think this answer is wrong, because of its claim about what can be defined in "two ASCII-pages or so". Many reals in $[0,10]$ can of course be defined by explicitly listing their binary digits, and a trillion (say) independent random bits is practically certain to define a number that cannot be expressed in "two ASCII-pages or so". (This supposes that after generating these bits, I would say that I have "thought of" the number.) – r.e.s. Nov 8 '15 at 20:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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