CODEWITHSUNDEEP
computation-theoryturing-machinescomputabilitydecidable
user4424299
user4424299

Reputation:

Prove that a specific language is not semidecidable

I have to prove that the language L = {< M >: |L(M)| <= 2016} is NOT semi-decidable. Now I thought of doing it like this:

Take a random alfabet E. Now there are an infinite number of words in E. We can only conclude that |L(M)| <= 2016 by passing every word from E* as an input to M. But because there are an infinite number of words, this means that we would have to pass an input to M an infinite number of times. But this implies that Turing Machine that performs these checks ends up in an infinite loop, and thus never returns accepts nor rejects it's input. The language L is thus not semi-decidable.

But I think that this might not be formal enough? Mainly because I just assume that the Turing Machine that checks this language will let M run on every word from E*. Is this assumption valid, or should I be more formal in this?

Upvotes: 0

Views: 1650

Answers (1)

Patrick87
Patrick87

Reputation: 28312

Consider the complement of L: the language of Turing-machine encodings whose languages contain more than 2016 strings. We can easily prove this language is semi-decidable. Given this fact, assume that L is also semi-decidable. Because L and its complement are both semi-decidable, we have an effective procedure for deciding each: run the TMs for L and its complement alternately, and one will eventually list the input.

To see that the complement of L is semi-decidable, imagine a TM that executes one step of M on every possible input, alternating moves so that each string is eventually processed by arbitrarily many moves of the TM. The order in which it would visit the inputs would be like:

e,
e, 0,
e, 0, 1,
e, 0, 1, 00, 
e, 0, 1, 00, 01, ...

Clearly, any string of input will eventually be processed every possible number of times. Our machine, which is simulating M running on all possible input strings, one step at a time, will eventually find 2017 strings have cause M to halt-accept, or it will run forever. If it finds 2017 strings that works, it halt-accepts.

Upvotes: 0

Related Questions