Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There are infinite many such strings, so that alone can't be used to prove the Turing machine of k states can check all strings. So that leaves open the original question, how do we know that a Turing machine of k states is able to have one of the stated outcomes for any possible bit string?


> There are infinite many such strings

And they can be enumerated by a finite program. For example, in lazily evaluated pseudocode:

    bits = ["0", "1"]
    bitstrings = bits + [(bit + suffix for bit in bits) for suffix in bitstrings]




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: