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

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

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.

edited ago
How is infinite loop possible without a left move of TM?
My mistake, unidirectional movement will not cause a loop. I will correct it.

+1 vote