-1
$\begingroup$

M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.

Why is {M : |L(M)| <= 330} not CE?

I can't seem to understand the logic why it is not CE, wouldn't it be CE since if it goes over 330, then we just halt?

Here they mention that its complement is CE, then by Rice Theorem, |L(M)| <= 330} is not CE, but I still don't understand why the same logic that was used to prove its complement is CE, can't be applied to "Is |L(M)| <= 330} is CE?".

Improve this question
$\endgroup$
1
  • $\begingroup$ I suggest you try writing out the proof that this language is CE, and checking each step to see if it follows. $\endgroup$
    – D.W. ♦
    Commented Apr 17, 2021 at 1:54

1 Answer 1

Reset to default
0
$\begingroup$

I can't seem to understand the logic why it is not CE, wouldn't it be CE since if it goes over 330, then we just halt?

The issue is what we do next: does halting correspond to "IN" or "OUT"?

A c.e. language is one for which we have an algorithm halting on exactly those inputs in the language. However, the "wait until you see 331, then halt" algorithm here halts on exactly those inputs not in the language. Like c.e.-ness this is a kind of "half-computability" property, but it's the other half: this is an example of a co-c.e. language.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh, I think i get it now, correct me if I am wrong but because L(M) only accepts 330 and less and because we can test an infinite amount of strings to see if L(M) accepts, then unless it goes over 330, we would never know if it truly only accepts 330 or less. $\endgroup$
    – paul lacher
    Commented Apr 17, 2021 at 14:24

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.