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

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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