0
$\begingroup$

I have two questions as in the title:

  1. TM M accepts some string of length greater than 100
  2. TM M accepts some string of length at most 100

Since 1. is infinite, we can rephrase question as "does TM accept a string", which is clearly undecidable and there are many proofs for that.

2nd question on the other hand is finite and all finite languages are decidable.

Is my reasoning correct? I can't find any confirmation of my theories.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ For starters yes if you know a language is finite it's decidable. But the problem of given a turing machine description telling whether the size of the language it accepts is finite, is an undecidable problem. So your reasoning is flawed. $\endgroup$
    – advocateofnone
    Nov 13, 2015 at 20:36
  • 1
    $\begingroup$ As for hint: see Rice theorem. $\endgroup$
    – advocateofnone
    Nov 13, 2015 at 20:41
  • $\begingroup$ With Rice's Theorem we can e.g. prove that L(M) contains only even (or odd) length strings. String of length at most 100 are the sum of those two (even and odd strings) which leads that in similar way we can prove 2nd question. What about the 1st one? Is the reasoning the same as for the 2nd question (proof with Rice's theorem) $\endgroup$
    – Dick Tracy
    Nov 13, 2015 at 20:58

1 Answer 1

Reset to default
2
$\begingroup$

I might be wrong ( ignore if you understand it correctly, I am beginner myself ), but I think you are misunderstanding the Rice Theorem. Broadly speaking any non-trivial property of the languages recognized by Turing machines is not decidable. A property is trivial if it holds for all or for none of the languages recognized by Turing machines. There are various posts explaining/regarding the theorem. For example I referred to the answer here How to show that a function is not computable? while learning the theorem. ( Skip to end if you only needed hint )
Coming to your case, the languages are $L_1=\{\langle M \rangle \;| \; \text{M accepts some string of length greater than 100} \}$ and $L_2=\{\langle M \rangle \;| \; \text{M accepts some string of length less than equal to 100} \}$
It is not difficult to see that in both the cases you are trying to decide non-trivial properties and thus both $L_1$ and $L_2$ are undecidable. As for your reasoning it is flawed as I commented, because knowing that size of a language is finite and being able to construct a Turing machine deciding it, is different from being able to decide whether an arbitrary Turing machine recognizes a language of finite size.
On a side note you could have approached the problem by first seeing that if both of the languages were decidable, the halting problem would become decidable which we no is not true.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.