0
$\begingroup$

I came across following problem:

  1. $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
  2. $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}$

Which one Recursively Enumerable (RecEn)? Which one Recursive (Rec)?

I feel both are not recursively enumerable and hence not recursive. We may list strings in some order and run Turing machine on them. But we may never come across two strings of same length accepted by same TM. So we cannot answer both questions "accepts two strings of different length" and "acceptes at least two strings of different length". Am I correct? Also is my approach correct?

$\endgroup$
1
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Mar 7, 2020 at 5:41

1 Answer 1

0
$\begingroup$

If (1) means exactly two strings of different lengths, not r.e. (2) is r.e.: guess two strings, check their lengths are different, verify that $M$ accepts both.

Use the extension to Rice's theorem to prove (1) isn't r.e.

$\endgroup$

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.