1,825 views
1 votes
1 votes
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 ??

4 Answers

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

edited by
0 votes
0 votes
both A ,B resembles MEMBERSHIP algorithm problem ,but in TM MEMBERSHIP algorithm is UNDECIDABLE.

so, A,B are UNDECIDABLE and more over every UNDECIDABLE languages are TURING RECOGNIZABLE

Related questions

2 votes
2 votes
1 answer
1
adwaitLP asked Sep 13, 2017
2,099 views
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
2 votes
2 votes
3 answers
3