The Gateway to Computer Science Excellence
+6 votes
1.3k views

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.

in Theory of Computation by Boss (16.2k points) | 1.3k views
+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.
0
@sourav how is TM for Tno possible with dovetailing?
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.
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
Logic to apply second Rice theorem is not clear.
0

@ 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 ?

 

0
Hey! May I know where we can get good material and easy understandable material on trivial property and Rice's Theorem? This is getting confusing with each and every example.

2 Answers

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

by Boss (44.1k points)
0
What is interleaved mode?
+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

@Manu Thakur

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

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

 

by Boss (27.3k points)
edited by
0

@Deepakk Poonia (Dee)

perfect answer bhai 

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
198,087 comments
104,737 users