4,369 views
11 votes
11 votes

My Question 


$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$

I have to check that it is Turing Recognizable or not (i.e R.E)

My Approach/Doubt


Question taken from 

https://gateoverflow.in/7427/which-following-languages-recursively-enumerable-language

I tried solving it using Rice theorem -2,i.e showing non-monotonic property.

My $T_{yes}=\left \{ \epsilon \right \}$//as length $=0$,it make sense

My $T_{no}=$Aceepting string of length at least $100$

$T_{yes}\subset T_{no}$.

Hence it is not RE.But in the solution  it is R.E.

2 Answers

24 votes
24 votes

There are finite number of inputs with length less than or equal to 100. Now run the TM M in interleaved mode, the moment TM halts on any one input, stop and consider that TM in the language.

Hence It's RE because we have a TM for this language but NOT RECURSIVE because in worst case TM M keeps on running and doesn't halt.

Hence this language is RE.

8 votes
8 votes

Although this question has been solved by Arjun sir using definitions of recognizability and decidability.

But many might be wondering how to apply Rice's theorem on this problem. 


 

$L = \{⟨M⟩∣M \,\,\,is \,\,\, a \,\,\,TM\,\,\, and\,\,\, there\,\,\, exist\,\,\, an\,\,\, input\,\,\, whose\,\,\, length\,\,\, is\,\,\, less\,\,\, than\,\,\, 100, on \,\,\,which\,\,\, M\,\,\, halts \}$

We cannot directly apply Rice's theorem here because "Halting" does not necessarily mean "Acceptance".

So, we first need to do some reduction from the given "Halting on some input of length $<100$  " problem to "Accepting some input of length $<100$  ".

This is easy because we can simply make the Reject state as Accept state in the given TM M.


In General :

Halting Problem : $ Halt_{TM} =  \{ <M,w> |  M \,\,\, is \,\,\, a\,\,\, TM\,\,\, and\,\,\, M \,\,\,halts\,\,\,on \,\,\, input \,\,\,w \} $

Acceptance Problem : $ A_{TM} =  \{ <M,w> |  M \,\,\, is \,\,\, a\,\,\, TM\,\,\, and\,\,\, M \,\,\,accepts\,\,\, input \,\,\,w \} $

Reduction from "Halting problem to Acceptance Problem" :

Reducing $Halt_{TM}$ to $A_{TM}$ : Given a Turing machine $M$ and an input $w$, let $M′$ be the machine obtained from $M$ by

marking all rejecting states as accepting. Then

$⟨M,w⟩∈Halt_{TM}\,\,\, iff \,\,\,  ⟨M′,w⟩∈A_{TM} $

Reduction from "Acceptance problem to Halting Problem" :

Reducing $A_{TM}$ to $Halt_{TM}$ : Given a Turing machine $M$ and an input $w$, let $M′$ be the machine obtained from $M$ by

getting to an infinite loop at every rejecting state (by making every rejecting state a looping state). Then 

$⟨M,w⟩∈A_{TM} iff ⟨M′,w⟩∈Halt_{TM}$

https://cs.stackexchange.com/questions/70989/proving-that-the-halting-problem-is-not-turing-reducible-to-the-acceptance-probl


So, we can reduce the  "Halting on some input of length $<100$  " problem to "Accepting some input of length $<100$  " by simply making the Reject state as Accept state in the given TM $M.$

Now the language we consider is :

$L' = \{⟨M⟩∣M \,\,\,is \,\,\, a \,\,\,TM\,\,\, and\,\,\, there\,\,\, exist\,\,\, an\,\,\, input\,\,\, whose\,\,\, length\,\,\, is\,\,\, less\,\,\, than\,\,\, 100,  \,\,\,which\,\,\, M\,\,\, accepts \}$

Now, On this problem/language $L'$ we can apply Rice's theorem.

The Property $P$ here is "Accepts some input of length $<100$" which clearly is 

1. Non-trivial property of RE languages : $L(T_{yes}) = \{ ab \}, L(T_{no}) = \{ a^{100}b^{100} \}$

2. Monotonic property of RE languages : If any RE language satisfies the property P i.e. it contains some string of length $<100$ then All its superset languages will also contain that string and hence, all superset languages will satisfy the property P.

Non-trivial property of RE languages implies $L'$ is Non-Recursive/Undecidable. Hence, $L'$ is Not-REC, as we can reduce $L'$ to $L$ (by reducing acceptance problem to halting problem) so, it makes $L$ undecidable. 

But monotonic property doesn't imply anything about recognizability so we have to apply the definition of recognizability here to get the final answer which Arjun sir has explained in the following post :

https://gateoverflow.in/7427/which-following-languages-recursively-enumerable-language

 

edited by

Related questions

1 votes
1 votes
0 answers
2
Akriti sood asked Jan 15, 2017
2,387 views
L={<M | M is a turing machine and it takes less than 481 steps on some input>decidable or R.E??i think it is decidable..just confirm it pls
3 votes
3 votes
2 answers
3
8 votes
8 votes
3 answers
4
Akriti sood asked Dec 16, 2016
4,774 views
$L=\left \{ <TM | TM\ halts\ on\ every\ input\ \right \}$is above language Recursively enumerable or non recursively enumerable??