<p>No, the string need not be normal.  Take any uncomputable sequence and add two 0s between each term; now there are too many 0s for the sequence to be normal but it's still uncomputable.</p>

CC BY-SA 3.0
2011-10-26T17:44:33.717Z
Cool, but I still wonder what can be said about the number distribution, if anything?
Golmokorov
CC BY-SA 3.0
2011-10-26T18:18:02.763Z
You can pad the sequence as much as you like, so certainly you can make an arbitrary pattern as common or as rare as desired.  I can't think of any nontrivial distributional qualities such a sequence would necessarily have.
Charles
CC BY-SA 3.0
2011-10-26T17:15:43.387Z
2011-10-26T17:15:43.387Z
Charles
<p>If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite times as a subsequence at approriate rates etc?</p>

CC BY-SA 3.0
2011-10-26T13:52:16.077Z
What do you mean with pseudo-random? I don't think there is a common property, see the numbers [Omega of Chaitin](http://en.wikipedia.org/wiki/Chaitin%27s_constant). On the contrary, the number which at position $i$ outputs whether or not the TM $M_i$ halts is not a random number.
Gopi
CC BY-SA 3.0
2011-10-26T13:57:42.543Z
@Gopi Omega is listed as one of the examples of Martin-Löf random (normal) numbers.
Golmokorov
CC BY-SA 3.0
2011-10-26T14:09:49.967Z
The answers to [this question](http://cstheory.stackexchange.com/q/1263/30) address your own question, and generalizations of it.
Aaron Sterling
CC BY-SA 3.0
2011-10-26T14:10:21.593Z
@Golmokorov, this is why I added the last number (I don't know if it has a name, I read somewhere that it was called $\tau$) as a not random number.
Gopi
CC BY-SA 3.0
2011-10-26T15:48:26.497Z
The answer is no. There are uncountable many non-normal numbers but only countable many programs.
Golmokorov
CC BY-SA 3.0
2011-10-26T16:00:37.407Z
@AaronSterling does this count as a duplicate then ?
Suresh Venkat
CC BY-SA 3.0
2011-10-26T16:01:11.650Z
@Golmokorov: Or more explicitly, we can obtain a non-normal non-computable infinite string by e.g. interleaving any non-computable infinite string with the infinite string 000….
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-26T16:32:02.710Z
@Suresh: I suppose someone could answer it relating normality to Martin-Lof tests.  I don't consider it a duplicate, but I also don't consider it sufficiently different to answer instead of commenting. :-)  Not very helpful, I know.
Aaron Sterling
<randomness><kolmogorov-complexity><pseudorandomness><pseudorandom-generators>
Non-computable=>normal?
Golmokorov
# Non-computable=>normal?

(Asked by: username_0 on 2011-10-26)

If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite times as a subsequence at approriate rates etc?

**Tags:** randomness, kolmogorov-complexity, pseudorandomness, pseudorandom-generators
> **Comments:**
> **username_1**: What do you mean with pseudo-random? I don't think there is a common property, see the numbers [Omega of Chaitin](http://en.wikipedia.org/wiki/Chaitin%27s_constant). On the contrary, the number which at position $i$ outputs whether or not the TM $M_i$ halts is not a random number.  
> **username_0**: @Gopi Omega is listed as one of the examples of Martin-Löf random (normal) numbers.  
> **username_2**: The answers to [this question](http://cstheory.stackexchange.com/q/1263/30) address your own question, and generalizations of it.  
> **username_1**: @Golmokorov, this is why I added the last number (I don't know if it has a name, I read somewhere that it was called $\tau$) as a not random number.  
> **username_0**: The answer is no. There are uncountable many non-normal numbers but only countable many programs.  
> **username_3**: @AaronSterling does this count as a duplicate then ?  
> **username_4**: @Golmokorov: Or more explicitly, we can obtain a non-normal non-computable infinite string by e.g. interleaving any non-computable infinite string with the infinite string 000….  
> **username_2**: @Suresh: I suppose someone could answer it relating normality to Martin-Lof tests.  I don't consider it a duplicate, but I also don't consider it sufficiently different to answer instead of commenting. :-)  Not very helpful, I know.  

---

## 1 answers

### Answer by username_5 on 2011-10-26. Score: 6 | Accepted answer

No, the string need not be normal. Take any uncomputable sequence and add two 0s between each term; now there are too many 0s for the sequence to be normal but it's still uncomputable.

> **Comments:**
> **username_0**: Cool, but I still wonder what can be said about the number distribution, if anything?  
> **username_5**: You can pad the sequence as much as you like, so certainly you can make an arbitrary pattern as common or as rare as desired.  I can't think of any nontrivial distributional qualities such a sequence would necessarily have.  

---

