7 ms·
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 origin
by WindyLakeReturn 3y ago
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?
- nyssos 3y ago> 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]