edited by
416 views
0 votes
0 votes
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable?

Please explain.
edited by

2 Answers

0 votes
0 votes
Answer is : Not even partially Decidable i.e not even Turing Recognizable

Apply Rice Theorem.

The property TM accept Language of less than 100 strings is Non Trivial and also Non Monotonic.

Therefore it's not even Partially Decidable.

Related questions

1 votes
1 votes
1 answer
1