2
$\begingroup$

Let $\alpha \in (0,1): \quad \alpha=0.a_1a_2\cdots a_n \cdots \quad$ where the $a_n$ are numbers generated by a physical generator of genuinely random numbers (if it exists). Than it seems that $\alpha$ should be a noncomputable number. Is this statement true? I suppose yes, because we know that a sequence of random numbers cannot be generated by a Turing machine.

If this is true than we can ask if all non computable numbers can be generated by some extension of this procedure, e.g. using two random number generators that gives two numbers $n$ and $a_n$, and inserting $a_n$ in the position $n$ of the decimal part of a computable number.

Obviously this is not a practical process to write uncomputable numbers, but the sense of the question is if there exists a correspondence between sets of random numbers and non-computable numbers.

$\endgroup$
  • $\begingroup$ Can a Turing machine generate random numbers? $\endgroup$ – Kenny Lau May 7 '16 at 15:37
  • $\begingroup$ No. and this is the motif because I suppose that using a genuine physical random generator we can ''construct'' a non computable number. $\endgroup$ – Emilio Novati May 7 '16 at 15:41
  • $\begingroup$ @KennyLau the correct question should be: what is the proability that a randomly chosen real number (with uniform distribution) is turing computable? The answer is: $0$. $\endgroup$ – Marco Disce May 18 '16 at 17:38
  • $\begingroup$ Otherwise one could also speak of "random numbers" meaning "algorithmically random": en.wikipedia.org/wiki/Algorithmically_random_sequence $\endgroup$ – Marco Disce May 18 '16 at 17:41
4
$\begingroup$

Let $\alpha \in (0,1): \quad \alpha=0.a_1a_2\cdots a_n \cdots \quad$ where the $a_n$ are numbers generated by a physical generator of genuinely random numbers (if it exists). Th[e]n it seems that $\color{blue}{\alpha\text{ should be a noncomputable number}}$. Is this statement true?

If this can be understood as referring to an infinite sequence of unbiased ($p=\frac{1}{2}$) Bernoulli trials, then the answer is $\color{blue}{\text{Yes (with probability $1$)}}$, because of two facts:

  1. If random variables (r.v.s) $a_1,a_2,\ldots$ are i.i.d. uniformly distributed on the set $\{0,1\}$, then $\alpha=(0.a_1a_2\ldots)_2$ is a r.v. uniformly distributed on the real interval $[0,1]$. To see this, note that for any $x=(0.x_1x_2\ldots)_2\in[0,1]$,
    $$\begin{align}\{\alpha > x\} = & \{a_1>x_1\}\cup\\ &\{\{a_1=x_1\}\cap \{a_2>x_2\}\}\cup\\ &\{\{a_1=x_1\}\cap \{a_2=x_2\}\cap\{a_3>x_3\} \}\cup\\ &\ldots \end{align}$$ Now, $P(a_i >x_i) = \frac{1}{2}(1-x_i)$, so the probability of the above disjoint union is just $$\begin{align}P(\alpha>x) &= \frac{1}{2}(1-x_1) + \frac{1}{2^2}(1-x_2) + \frac{1}{2^3}(1-x_3)+\ldots\\ &= \sum_{i=1}^\infty \frac{1}{2^i} - \sum_{i=1}^\infty \frac{x_i}{2^i}\\ &= 1 - x\\ \therefore P(\alpha\le x) &= x \end{align} $$ therefore $\alpha$ is a r.v. uniformly distributed on $[0,1]$.

  2. If a r.v. $\alpha$ is uniformly distributed on $[0,1]$, then (a) $P(\alpha\in C) = 0$, and (b) $P(\alpha\in U)=1$, where $C$ (resp. $U$) is the set of computable (resp. uncomputable) reals in $[0,1].$ This is due to the fact that the interval $[0,1]$ is the disjoint union of $C$ and $U$, and that $C$ is countable, whereas $U$ is uncountable:

    a. $P(\alpha\in C) = P(\bigcup_{x\in C}\{\alpha=x\}) = \sum_{x\in C}P(\alpha=x) = 0$

    b. $1 = P(\alpha\in [0,1]) = P(\alpha\in (C\cup U)) = P(\alpha\in C) + P(\alpha\in U) = 0 + P(\alpha\in U)$

If this is true th[e]n we can ask if all non computable numbers can be generated by some extension of this procedure, e.g. using two random number generators that gives two numbers $n$ and $a_n$, and inserting $a_n$ in the position $n$ of the decimal part of a computable number.

If you did such finite insertions only finitely many times in the digits of a computable real, the result is still a computable real, because any such finite sequence of operations could be programmed. (On the other hand, if you did this infinitely many times--how, I don't know, since it couldn't be programmed-- then you may as well just throw out the computable real and replace it using the infinitely many "insertion" digits instead.)

$\endgroup$
2
$\begingroup$

There are only countably many Turing machines, and thus countably many sequences that they generate. For any iid sequence $X_n$ of random variables that is not almost surely constant, the probability of a particular sequence of values is $0$, and thus by countable additivity the probability of a Turing-computable sequence is $0$.

$\endgroup$

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.