The Gateway to Computer Science Excellence

+6 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

For Rice's theorem, the subset relation is for $L(T_{yes})$ and $L(T_{no})$. For your example is this holding?

0

@arjun sir , if i would use dovetailing , then i can construct a turing machine for $L(T_{no})$

.For $L(T_{yes})$ , if i would change my $L(T_{yes})$= {⟨M⟩∣Mis a TM and there exist an input whose length is atleast 1 , on which M halts}.Then will the **Rice theorem** won't hold?

+6

@sourav.

How Tyes $\subset$ Tno? (In your example)

Tno doesn't contain $\epsilon$.

I think we can't apply the second rice theorem here.

How Tyes $\subset$ Tno? (In your example)

Tno doesn't contain $\epsilon$.

I think we can't apply the second rice theorem here.

0

@arjun sir , For $T_{no}$We can run each string on each machine and keep adding a new string adding a new step to the old string, thus when we reach 100 string we can say "yes" to yes , as like we proved that

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs} as turing recognizable.

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs} as turing recognizable.

0

@sourav But if there is no such string which halts then even for 100 strings (or any one) the TM will never stop.

0

@Arjun sir , Exactly that's the point where i am confused , if $T_{no}$ is not turing recognizable , then how

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs} here https://gateoverflow.in/66/consider-the-following-languages

Turing recognizable .???.It should be applicable for this too.

0

This is non-trivial property of language. So it is Undecidable. And if we use dovetailing, then we can get all Turing machines which will halt on some input whose length is less then 100. But we fan not get those in our set who will not halt and go into infinite loop. so this problem is partially decidable and hence Turing Recognizable but not Turing Decidable.

0

@Arjun sir @Manu Thakur sir

we can apply rice theorem when we are given property of language of Turing machine

Here we have TM property not property of its language ,,how can we apply RICE's theorem here ?

+15 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**.

+2

here interleaved refers to dovetailing technique which means we try to generate one string if it is not getting done for some time we move to generate to another string

0

Cant we just check from given TM in input if there exist some path for all finite no of inputs with length less than or equal to 100, at which TM halts, without actually running the TM. If we get path for at least 1 input we can give in output and if we don't get after checking finite inputs, its not given in output.

Please suggest if this is possible. Thanks!

+3 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}$

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,258 answers

198,087 comments

104,737 users