Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests - Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests -
× DOWNLOAD NOW

Undecidable Problem about Turing Machine

If there isn’t a Turing machine that will always stop after a set amount of time to answer “yes” or “no,” then the problem cannot be resolved. No algorithm exists to find the solution to an undecidable problem given an input.

In this article, we will look more into the Undecidable Problem about Turing Machine according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.

Table of Contents

What is the Undecidable Problem about the Turing Machine?

All of the Turing machine’s unsolvable issues will be covered in this section. The reduction is employed to demonstrate whether or not the given language is desirable. In this section, we will first comprehend the idea of reduction before looking at a crucial theorem.

Reduction

When a problem P1 gets reduced to a problem P2, the solution to P2 solves P1, according to the reduction approach. P1 reduced P2 is the general term for an algorithm that transforms an instance of a problem P1 into an instance of a problem P2 with the same solution. As a result, if P1 is not recursive, then neither is P2. In a similar vein, if P1 is not recursively enumerable, then neither is P2.

Theorem

  1. If P1 gets reduced to P2, this is what would happen:
  2. P2 is equally undecidable if P1 cannot be decided.
  3. P2 is also non-RE if P1 is non-RE.

Proof

  1. Think about a P1 instance w. Next, create an algorithm that transforms instance w into instance x of P2 from instance w as input. Next, use that procedure to determine whether x is contained in P2. If the algorithm returns “yes,” then x is in P2, and similarly, we can claim that w is in P1 if the method returns “yes,” since P2 was derived after P1 was reduced (similar to how if the algorithm returns “no”, then x is not in P2 and w is not in P1 as well). This demonstrates that if P1 is intractable, then P1 is intractable as well.
  2. Here, P1 is not RE while P2 is. Create an algorithm that will decrease P1 to P2; however, P2 will be identified by this algorithm. This means that a Turing machine will exist, responding “yes” if the input is P2, but it may or may not halt if the input is not P2. Since we now know that one can change a w instance in P1 into an x instance in P2, apply a TM next to see if P2 contains x. If f x is approved, then w must likewise be accepted. This method explains a TM whose native language is P1. If w is in P1, then x is also in P2, and vice versa if w isn’t in P1. This demonstrates that P2 must likewise be non-RE if P1 is non-RE.

Empty and Non-Empty Languages

Languages can be divided into two categories: empty and non-empty languages. Let Le stand for an empty language and Lne for a language that is not empty. Let Mi be a TM and w be a binary string. If L(Mj) =, Mi will not accept input, and w will be in Le. Similarly, w is in Lne if L(Mj) is not the empty language. As a result, we may state:

Lne = {M | L(M) ≠ Ф}

Le = {M | L(M) = Ф}

The complement of Le and Lne is the other one.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.

Also Explore,