0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The answers to this question address your own question, and generalizations of it. $\endgroup$ – Aaron Sterling Oct 26 '11 at 14:09
  • 1
    $\begingroup$ The answer is no. There are uncountable many non-normal numbers but only countable many programs. $\endgroup$ – Golmokorov Oct 26 '11 at 15:48
  • 1
    $\begingroup$ @AaronSterling does this count as a duplicate then ? $\endgroup$ – Suresh Venkat Oct 26 '11 at 16:00
  • 1
    $\begingroup$ @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…. $\endgroup$ – Tsuyoshi Ito Oct 26 '11 at 16:01
  • 2
    $\begingroup$ @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. $\endgroup$ – Aaron Sterling Oct 26 '11 at 16:32
6
$\begingroup$

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.

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

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.