0

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?

Golmokorov
  • 3
  • 2
  • What do you mean with pseudo-random? I don't think there is a common property, see the numbers Omega of Chaitin. On the contrary, the number which at position $i$ outputs whether or not the TM $M_i$ halts is not a random number. – Gopi Oct 26 '11 at 13:52
  • @Gopi Omega is listed as one of the examples of Martin-Löf random (normal) numbers. – Golmokorov Oct 26 '11 at 13:57
  • 3
    The answers to this question address your own question, and generalizations of it. – Aaron Sterling Oct 26 '11 at 14:09
  • @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 Oct 26 '11 at 14:10
  • 1
    The answer is no. There are uncountable many non-normal numbers but only countable many programs. – Golmokorov Oct 26 '11 at 15:48
  • 1
    @AaronSterling does this count as a duplicate then ? – Suresh Venkat Oct 26 '11 at 16:00
  • 1
    @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 Oct 26 '11 at 16:01
  • 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. – Aaron Sterling Oct 26 '11 at 16:32

1 Answers1

6

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.

Charles
  • 1,735
  • 12
  • 23
  • Cool, but I still wonder what can be said about the number distribution, if anything? – Golmokorov Oct 26 '11 at 17:44
  • 2
    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 Oct 26 '11 at 18:18