- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Before we understand about the decidable and undecidable problems in the theory of computation (TOC), we must learn about the decidable and undecidable language. Hence, let us first see what do you mean by decidable language.

A language L is called decidable if there is a decider M such that L( M) = L.

Given a decider M, you can learn whether or not a string w ∈ L(M).

Run M on w.

Although it might take a long time, M will accept or reject w.

The set R is the set of all decidable languages.

L ∈ R if L is decidable.

A decision problem P is undecidable if the language L of all yes instances to P is not decidable.

An undecidable language may be partially decidable but not decidable. Suppose, if a language is not even partially decidable, then there is no Turing machine that exists for the respective language.

Find whether the problem given below is decidable or undecidable.

“Let the given input be some Turing Machine M and some string w. The problem is to determine whether the machine M, executed on the input string w, ever moves its readhead to the left for three delta rules in a row.”

Define M' is a Turing machine that takes a pair (M,w) as input, where M is a Turing machine recognized by M' and w is the input to M.

Whenever the head of simulated machine M moves to left while processing input w , M' stops and accepts (M,w)

For a particular input to M' (M,w), construction the Turing machine P is −

P executes M' on (M,w)

P stops and accepts any input if M' accepts (M,w)

We have tried to reduce the Universal Turing Machine U to P, because we know that L(U) is not decidable, and also we conclude that L(P) is not decidable. Consequently, M' is not decidable.

Let us assume that this problem is decidable, and then we have to show that the altering turing machine (ATM) is also decidable −

ATM = { M is a TM and M accepts w}.

Let R be a Turing machine which decides the leftmost problem.

That is, R decides the language

leftmost = { M on input w ever attempts to move its head left when it's head is on the left-most tape cell }.

Now, the idea is to construct a Turing machine S which decides ATM in such a way that it uses R.

On input, S first modifies machine M to M´, so that M´ moves its head to the left from the left-most cell only when M accepts its input.

To ensure that during its computation M´ does not move the head left from the left-most position,

First machine M´ shifts the input w one position to the right, and places a special symbol on the left-most tape cell. The computation of M´ starts with the head on the second tape cell.

During its computation M´ ever attempts to move its head to the left-most tape cell, M´ finds out by reading the special symbol and puts the head back to the second cell, and continues its execution. If M enters an accept state, then M´ enters a loop that forces the head to always move to the left.

After S has constructed M´ it runs the decider R on input < M´; w>.

If R accepts then S accepts, otherwise if R rejects then S rejects.

Therefore, ATM is decidable, which is a contradiction.

- Related Questions & Answers
- What are the undecidable problems in TOC?
- Explain the main problems in concurrency control(DBMS)
- Differentiate between recognizable and decidable in the Turing machine?
- Explain the problems for equivalence of two regular expressions.
- Profit and loss Problems using C
- Parallel RLC Circuit: Analysis and Example Problems
- Series RLC Circuit: Analysis and Example Problems
- What are the most common teenage problems?
- Why the NP-complete problems are significant?
- Introduction to Miscellaneous Problems
- What are Agency Problems?
- Phobias: Embarrassing yet Compulsive Problems
- Dealing with Problems Compiling MySQL
- What are the problems created due to excess calcium?
- What are the routing potential problems in Computer Architecture?

Advertisements