The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
221 views
A = { (M, w) | M is a TM that on input w, tries to move its head past the left end of the input }

B = { (M, w) | M is a TM that on input w, moves its head left at least once, at some point}

how to decide that a problem is decidable or undecidable , recognisable or unrecognisable ??
asked in Theory of Computation by Active (1.1k points) | 221 views
both undecidable as both are non trivial property of Turing m/c.

Regarding Turing recognizablity,

A=Not RE

B=RE using dovetailing
both A and B are refereing to a non semantic property . Rice theorem( for undecideability) states only non trival semantic properties  bearing langauge to be undecidable . So Rice theorem wont apply here right?   How did you decide whether it is decideable or even recognizable?

Also can you state what are the factors one can look for in langauge to deduce  such conclusion.. as even knowing Rice thoerom , i cant solve them with confidence. I m so confused about this topic.

1.

  • First of all you need to check that a language is turing recognizable or not .How can you check it
  • You have to analyse it that can you answer always "yes", when it is yes?don't worry about its no,then it will be RE else non-RE
  • However if you can also answer always "no"  when its no , then it will be  Recursive and hence decidable.
  • Another way to analyse this is with help of Rice theorem -2 http://gatecse.in/rices-theorem/
  • if you manage to prove that is non-RE , then it will not be decidable

2.

  • If you manage to prove that it is RE, then it may be decidable or undecidable.you can check that with  Rice theorem 1.
  • if you managed to Prove that the language is one of the non trivial property of turing machine then it will be undecidable.http://gatecse.in/rices-theorem/
  • Its not that easy to analyse it  in one go , you need to look for examples which are decidable/undecidable.How they become undecidable,After solving few solved examples,try to solve on your own.
the conditions mentioned in the question are non semantic ie those condition are not related to the language but are related to TM .  So Can we say that non semantic properties are non trival . Hence the language with such specification are by default undecidable.

 

non semantic  properties example:

L= { w | TM has 10 states}

L= { w | TM has 10 states,TM w has 10 states}

Trivial property is defined for RE sets.we cannot define/make use of trivial propert here.

This problem is decidable .

Hint Enocode the states in binary form i.e for $10$ states it will be

$0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010$

if we have $11$ on msb side then it must be rejected .

@sourav Rice's theorem is applicable only for r.e. set -- not for TMs.
sir, L= { w | TM has 10 states} is decidable ?is my expanation correct above?
what is the relation between w and TM?
sorry i pasted his question directly.I assumed

L= {w | TM has 10 states}, w is a T.M which has 10 states
That means "w" is an encoding of TM-- this encoding will have the information for states. We can check it and see if the number of states is 10 -- hence decidable. This is not a trivial property of any set. If we say given a r.e. set if it has a TM with 10 states, then it is a trivial property.

okk sir , so the golden point is -:

A Property of R.E language is simply a set of RE language.

I will update answer ,sir encoding part explanation is ok above?

 

3 Answers

0 votes
answered by Veteran (19.5k points)
Hi, if you don't have your own answer but instead having some reference links pleae try not to post as answer. Thanks
how to decide that a problem is decidable or undecidable , recognisable or unrecognisable ??

Sorry Debashish Deka Sir , I will take care next time......

Not a sir.

You can use comment section. It's always better to have Actual content rather than redirect link in answer. Thanks for understanding.
ok......
0 votes
Well, I don't know which kind of Turing machine these are, as it is just moving its head instead of producing some output and there is no language definition given for acceptance.

However, a problem is called decidable if there is an algorithm to decide the set membership problem. Let us say the language accepted by the given Turing machine M is L has then given an input if we can decide in finite time that input belongs to the language (acceptance i.e. halting on an accepting state) or input do not belong to the language (rejection i.e. halting on a rejecting state). That problem would be called decidable.

Remember halting on rejection is also important here if it is looping forever and not halting on a non-accepting input then it is undecidable. And the language which is decidable is called recursive.

We need to get either a 'YES' or 'NO' answer in our membership problem to be decidable, looping forever would not be good enough for rejection.

As far as the given two machines are concerned, in case of A when machine tries to move its head to the left of the input, it really depends on the input, if it is finite then it would be clear that machine is able to do it(YES) or not been able to do it(NO). If the input is infinite machine would not halt hence undecidable.

When we take the case of B which moves its head to the left at least once, it is clearly decidable, no matter whether the input is finite or infinite, it would either be successful in moving to the left once or not i.e. it will halt.
answered by (165 points)
0 votes

A problem is said to decidable if there exists a halting Turing machin(TM) which can solve the problem (definitely say YES or NO). Any problem which has a definite algorithm (algorithm with finite steps) can be expressed as a halting TM, hence they are decidable.

In contrary, a language/problem is said to be undecidable if there exists a TM which can accept a string if it is part of the language and reject or loop infinitely if the string is not part of the language. 

A. Undecidable. Because it might fall into an infinite loop right after scanning the first input symbol and never reaches to the left of the given input. 
B. Decidable. A unidirectional movement of head towards right will not create a loop. Hence even if the TM falls into infinite loop, it proves that it was able to move it head to the left at some point of the input. 

answered by (63 points)
edited by
How is infinite loop possible without a left move of TM?
My mistake, unidirectional movement will not cause a loop. I will correct it.


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

29,115 questions
36,925 answers
91,927 comments
34,782 users