GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
175 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 Junior (753 points)   | 175 views
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 (14.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 (91 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 even you give finite input 'w' to the TM, it might fall into an infinite loop within its states. 
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 of the input. 

answered by (37 points)  
edited ago 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.


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2058 Points

  5. A_i_$_h

    1990 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,037 questions
33,646 answers
79,693 comments
31,069 users