Examples of Undecidable Problems

Examples of Undecidable Problems

Undecidable problems are problems for which no algorithm can be constructed that will always lead to a correct yes-or-no answer. This topic will explore several well-known examples of undecidable problems, illustrating their significance in theoretical computer science.

The Halting Problem

The Halting Problem is one of the most famous undecidable problems. It can be stated as follows: given a description of an arbitrary computer programme and an input, determine whether the programme will eventually halt (stop running) or continue to run indefinitely.

Formal Definition

Let P be a programme and I be an input. The Halting Problem asks whether there exists a function H(P, I) such that:

• If P halts on input I, then H(P, I) returns true.
• If P does not halt on input I, then H(P, I) returns false.

Proof of Undecidability

To prove that the Halting Problem is undecidable, we use a proof by contradiction. Assume there exists a function H that decides the Halting Problem. We can construct a new programme, called D, as follows:

function D(P):
    if H(P, P) is true then
        loop forever
    else
        halt

The programme D takes another programme P as input. If H determines that P halts when given itself as input, D will run indefinitely. If H determines that P does not halt, D will halt. Now, consider what happens when we run D with itself as input:

H(D, D)

If H(D, D) is true, D will run indefinitely, which contradicts H's output. If H(D, D) is false, D will halt, which also contradicts H's output. Thus, we conclude that H cannot exist, proving that the Halting Problem is undecidable.

The Post Correspondence Problem

The Post Correspondence Problem (PCP) is another classical undecidable problem in theoretical computer science. It involves matching sequences of strings.

Formal Definition

Given two lists of strings, A = {a₁, a₂, ..., a_n} and B = {b₁, b₂, ..., b_n}, the question is whether there exists a sequence of indices (i₁, i₂, ..., i_k) such that:

a_i1 a_i2 ... a_ik = b_i1 b_i2 ... b_ik

Example

Consider the following lists:

• A = {"ab", "a"}
• B = {"ba", "a"}

We want to find a sequence of indices that makes the concatenated strings equal. The sequence (1, 2) gives:

a1 a2 = "ab" + "a" = "aba"

b1 b2 = "ba" + "a" = "baa"

These are not equal, so we try (2, 1):

a2 a1 = "a" + "ab" = "aab"

b2 b1 = "a" + "ba" = "aba"

These are also not equal. After testing all combinations, we can conclude that there is no such sequence for the given lists. The PCP is undecidable because no algorithm can determine a solution for all possible lists.

Reducibility and Undecidable Problems

Reducibility is a method used in theoretical computer science to show that one problem is at least as hard as another. If we can reduce a known undecidable problem to a new problem, we can conclude that the new problem is also undecidable.

Example of Reducing the Halting Problem

Suppose we have a new problem, Z, and we want to show that Z is undecidable. If we can construct a function R that transforms instances of the Halting Problem into instances of Z, we can conclude that Z is undecidable. This is done by demonstrating that if we could decide Z, we could also decide the Halting Problem, which we know is impossible.

Other Notable Undecidable Problems

In addition to the Halting Problem and the Post Correspondence Problem, there are other notable undecidable problems, including:

• The Entscheidungsproblem: This problem asks whether there is an algorithm that can determine the truth of any mathematical statement. It is undecidable due to Gödel's incompleteness theorems.
• The problem of determining whether a given context-free grammar generates an empty language.
• The problem of determining whether two context-free grammars generate the same language.

Summary

• Undecidable problems are those for which no algorithm can provide a correct yes-or-no answer.
• The Halting Problem is a key example of an undecidable problem.
• The Post Correspondence Problem is another example of an undecidable problem involving string sequences.
• Reducibility is a technique used to prove the undecidability of new problems.
• Other notable undecidable problems include the Entscheidungsproblem and problems related to context-free grammars.

Check your understanding

1. What is the Halting Problem and why is it significant?
2. Explain the Post Correspondence Problem with an example.
3. What does it mean for a problem to be undecidable?
4. How does reducibility help in proving that a problem is undecidable?