The Gateway to Computer Science Excellence
0 votes
298 views
Problem : It is undecidable whether an arbitrary Turing Machines halt within 10 steps?

Let consider Two Turing machine in which first one it is halt in 10 steps while in other it is not , so as it is undecidable.

@arjun sir ,@bikram sir or @others
in Theory of Computation by Active (4.1k points) | 298 views
+1
suppose you run TM for 10 steps;
if it halt in 10 steps you can say yes;
if it is not halt then you can say no ,
so means you can decide then why undeciadable.
0
what  i assume in first case it halt and other one it is in loop .

Now So it is undecidable?

@Anu007 plz describe means of Trivial and non-trivial in terms of rice theorem and monotonic and non-monotonic also.
+1
you can run on same machine and if you say yes and no then decidable.

 

Trivial : If all TM behave same for any property. like machine has 2 states,

Non trivial:  ALL Tm does not behave same for Any property.
0
trivial means it accepts every string of that language
non trivial means it accepts some string of that language but not all
0
@srestha  so you want to say that

Trivial means :: L(G) = 0*1* than all strings (phi,0,1,00,11 ....etc) is accepted by TM

Non Trivial Means ::  while for this language some strings is accepted by TM like (phi,0,1) only other are rejected .

Rt?
0
@Anu007 reference to above question , I am asking you

As in first Turing Machine it is halting in 10 steps

while in second it is not halt in 10 steps

so I think this is non-trivial property ?
0
Also tell what is meant by monotonic and non-monotonic means ?
+2
not like that
 Turing Machines halt within 10 steps
it is TM property. So, TM property is always trivial
non trivial case are the case which we examine for the language of TM
like language has atleast 10 states.....etc
+3
yep! @srestha said correctly! Rice's theorem is meant to be applied on the language but not on the properties of a  Turing machine, in this case whether a TM halts with in 10 steps or not is a property of a TM and we can answer this question either yes or no always in finite time.
+2
thanks :)
0

@ Manu Thakur

how r u searching question?

I mean how u find 6 days previous question?

+1
@srestha i didn't search, this post was in the recent activities, but don't know how :D

Please log in or register to answer this question.

Related questions

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,370 answers
198,506 comments
105,275 users