Turing Machines and Decidability

This chapter rigorously introduces Turing Machines as the universal model of computation, laying the theoretical groundwork for understanding algorithmic limits. It systematically distinguishes between computable and noncomputable functions and establishes the fundamental concepts of decidability and undecidability. Mastery of these principles is critical for advanced examinations in theoretical computer science, forming a cornerstone of the M.Sc./Ph.D. curriculum.

---

Chapter Contents

|

| Topic |

---

We begin with Computable and Noncomputable Functions.

Part 1: Computable and Noncomputable Functions

This unit explores the theoretical limits of computation, identifying problems that cannot be solved by any algorithm and classifying functions based on their computability. Understanding these boundaries is crucial for advanced computer science.

---

Core Concepts

1. Turing Machines and Computable Functions

A Turing Machine (TM) is a mathematical model of computation that defines an abstract machine manipulating symbols on a strip of tape according to a table of rules. A function $f: \Sigma^$ \to \Gamma^ is computable (or recursive) if there exists a Turing Machine that, for every input $w$ in the domain of $f$, halts with $f(w)$ on its tape.

Worked Example:

Consider the function $f(n) = n+1$ for a non-negative integer $n$, represented in unary. We demonstrate a conceptual Turing Machine that computes this function.

Step 1: Initial configuration

The input tape contains $n$ '1's, followed by a blank symbol, e.g., `_111_` for $n=3$.

>

Step 2: Move to the rightmost '1'

The TM moves its head to the right, skipping all '1's, until it finds the first blank symbol.

>

Step 3: Overwrite the blank with '1'

The TM replaces the blank symbol with a '1'.

>

Step 4: Move left and halt

The TM moves its head one position to the left, then halts in an accepting state.

>

Answer: The TM successfully computes $n+1$ by adding an additional '1' to the unary representation of $n$.

:::question type="MCQ" question="Which of the following best describes a computable function?" options=["A function whose output can be described by a finite set of rules.","A function for which there exists a Turing Machine that halts on all inputs with the correct output.","A function that can be computed by any physical computer.","A function that can be expressed using only basic arithmetic operations."] answer="A function for which there exists a Turing Machine that halts on all inputs with the correct output." hint="Recall the formal definition of a computable function in the context of Turing Machines." solution="A computable function is formally defined as one for which a Turing Machine exists that can compute its output for all inputs in its domain. The option 'halts on all inputs with the correct output' aligns with a total computable function, which is a common interpretation when not specified as partial. The other options are either too vague or incorrect in the formal sense of computability theory. For a partial computable function, the TM may not halt if the input is outside its domain."
:::

---

2. Church-Turing Thesis

The Church-Turing Thesis states that any function that can be computed by an algorithm can be computed by a Turing Machine. It asserts the equivalence of all "reasonable" models of computation with the Turing Machine model. This is a thesis, not a theorem, as it relates a formal concept (Turing Machine) to an informal one (algorithm).

Worked Example:

Consider a problem of finding the shortest path in a graph using Dijkstra's algorithm.

Step 1: Algorithm definition

Dijkstra's algorithm is a well-defined sequence of steps to find the shortest path. It involves graph traversal, distance updates, and priority queue operations.

>

Step 2: Implication of Church-Turing Thesis

Since Dijkstra's algorithm is a precise, step-by-step procedure that can be executed mechanically, the Church-Turing Thesis implies that a Turing Machine exists that can simulate this algorithm.

>

Answer: The Church-Turing Thesis implies that if an algorithm exists for a problem, a Turing Machine can solve it. Therefore, a Turing Machine can compute the shortest path in a graph using Dijkstra's algorithm.

:::question type="MCQ" question="What is the primary implication of the Church-Turing Thesis?" options=["All functions can be computed by a Turing Machine.","Turing Machines are the most powerful computational model known.","Any problem solvable by an algorithm can be solved by a Turing Machine.","Computers will eventually be able to solve all mathematical problems."] answer="Any problem solvable by an algorithm can be solved by a Turing Machine." hint="The thesis connects the informal notion of an 'algorithm' to the formal model of a 'Turing Machine'." solution="The Church-Turing Thesis posits that the class of functions computable by any 'effective method' (i.e., algorithm) is exactly the class of functions computable by a Turing Machine. This means that if we can describe an algorithm for a problem, a Turing Machine can solve it. It does not claim that all functions are computable, nor does it make predictions about future computer capabilities."
:::

---

3. Universal Turing Machine

A Universal Turing Machine (UTM) is a special Turing Machine that can simulate the behavior of any other arbitrary Turing Machine on any arbitrary input. It takes as input a description of another Turing Machine $M$ and an input $w$ for $M$, and then simulates $M$'s behavior on $w$.

Worked Example:

Consider a UTM $U$ operating on an input tape that contains the encoded description of a Turing Machine $M$ and its input $w$.

Step 1: Input tape configuration

The tape is divided into sections: one for $M$'s description, one for $M$'s current tape content, and one for $M$'s current state.

>

Step 2: Simulation cycle

The UTM $U$ reads $M$'s current state $q_i$ and the symbol under $M$'s simulated head. It then consults $M$'s encoded transition function $\delta_M$.

>

Step 3: Update $M$'s simulated configuration

Based on $\delta_M$, $U$ updates $M$'s simulated tape content, moves $M$'s simulated head, and changes $M$'s simulated state. This cycle repeats.

>

Answer: The UTM $U$ effectively simulates $M$ on $w$ by interpreting $M$'s rules and applying them to $M$'s simulated tape, demonstrating its role as a general-purpose computer.

:::question type="MCQ" question="What is the primary function of a Universal Turing Machine?" options=["To solve the Halting Problem for any Turing Machine.","To compile high-level programming languages into machine code.","To simulate any arbitrary Turing Machine on any given input.","To prove the undecidability of certain computational problems."] answer="To simulate any arbitrary Turing Machine on any given input." hint="The 'universal' aspect implies it can act like any other TM." solution="A Universal Turing Machine (UTM) is designed to take the description of any other Turing Machine $M$ and an input $w$ for $M$, and then simulate $M$'s computation on $w$. This makes it a general-purpose computer, capable of performing any computation that any other TM can perform."
:::

---

4. Undecidability and Noncomputable Functions

A problem is undecidable if no algorithm (Turing Machine) exists that can solve it for all possible inputs. A function is noncomputable if no Turing Machine can compute it. These concepts define the limits of what computers can do.

Worked Example:

Consider the problem of determining if a given C++ program will ever output the string "Hello World!".

Step 1: Formulate as a decision problem

We want to know if for a given program $P$, does $P$ output "Hello World!"? This is a yes/no question.

>

Step 2: Consider the nature of the problem

To solve this, a hypothetical algorithm would need to analyze the program's execution path, including loops, conditional statements, and function calls, for all possible inputs to $P$. This involves predicting the program's behavior over potentially infinite execution paths.

>

Answer: This problem is undecidable. An algorithm cannot, in general, determine if an arbitrary program will ever print a specific string because it would require solving a variant of the Halting Problem or a related undecidable property (like a non-trivial semantic property of programs, as per Rice's Theorem).

:::question type="MCQ" question="Which of the following is an example of an undecidable problem?" options=["Determining if a given string is a palindrome.","Determining if a given context-free grammar is ambiguous.","Determining if a given regular expression generates an infinite language.","Determining if a given finite automaton accepts a particular string."] answer="Determining if a given context-free grammar is ambiguous." hint="Undecidable problems often involve infinite state spaces or properties that require simulating arbitrary computation." solution="Determining if a given context-free grammar is ambiguous is a known undecidable problem. The other options are decidable: palindromes can be checked by a simple algorithm, regularity of infinite languages is decidable, and FA acceptance is decidable (e.g., by simulating the FA or constructing a product automaton)."
:::

---

5. The Halting Problem

The Halting Problem asks whether, given a description of an arbitrary Turing Machine $M$ and an input $w$, $M$ will halt (finish its computation) or run forever when started on $w$. This problem is famously undecidable.

Worked Example: Proof by contradiction for the Halting Problem.

Step 1: Assume $H$ is a decider for $HALT$

Suppose there exists a Turing Machine $H$ that decides the Halting Problem. $H$ takes $\langle M, w \rangle$ as input and halts, accepting if $M$ halts on $w$, and rejecting if $M$ does not halt on $w$.

>

Step 2: Construct a new TM, $D$

Using $H$, construct a new Turing Machine $D$ that takes an encoding of a TM $\langle M \rangle$ as input. $D$ does the following:

>

Step 3: Run $D$ on its own description $\langle D \rangle$

Now, consider what happens when $D$ is run with its own description $\langle D \rangle$ as input.

>

Step 4: Analyze the outcome

>

Answer: Both possible outcomes lead to a contradiction. Therefore, our initial assumption that $H$ exists must be false. The Halting Problem is undecidable.

:::question type="MCQ" question="The Halting Problem asks whether a given Turing Machine $M$ will halt on a given input $w$. Why is this problem considered undecidable?" options=["Because it requires an infinite amount of memory.","Because no algorithm can exist that determines for all $M$ and $w$ if $M$ halts on $w$.","Because the input $w$ can be arbitrarily long.","Because it is impossible to write a program that simulates another program."] answer="Because no algorithm can exist that determines for all $M$ and $w$ if $M$ halts on $w$." hint="Recall the proof by contradiction, which demonstrates the impossibility of such an algorithm." solution="The Halting Problem is undecidable because it has been proven, typically through a diagonalization argument (as shown in the worked example), that no Turing Machine (and by the Church-Turing Thesis, no algorithm) can exist that can correctly determine for all possible pairs of Turing Machine $M$ and input $w$ whether $M$ will halt or loop indefinitely on $w$. The other options are incorrect; memory is not the core issue, input length is handled by TMs, and program simulation is possible (Universal TM)."
:::

---

6. Reducibility

Reducibility is a technique used to prove the undecidability of problems. If problem $A$ can be reduced to problem $B$ (denoted $A \le_m B$), and $A$ is known to be undecidable, then $B$ must also be undecidable. This means an algorithm for $B$ could be used to solve $A$, which is a contradiction.

Worked Example: Proving that $L_{\neg HALT} = \{ \langle M, w \rangle \mid M \text{ does not halt on } w \}$ is undecidable.

Step 1: Assume $L_{\neg HALT}$ is decidable

Suppose there exists a decider TM $R$ for $L_{\neg HALT}$. This means $R$ halts on all inputs and accepts $\langle M, w \rangle$ if $M$ does not halt on $w$, and rejects otherwise.

>

Step 2: Construct a decider for $HALT$ using $R$

We know $HALT = \{ \langle M, w \rangle \mid M \text{ halts on } w \}$ is the complement of $L_{\neg HALT}$. If $R$ decides $L_{\neg HALT}$, we can construct a decider for $HALT$ as follows:

>

Step 3: Contradiction

The constructed TM is a decider for $HALT$. However, we know from the Halting Problem that $HALT$ is undecidable. This is a contradiction.

>

Answer: Since our assumption leads to a contradiction, $L_{\neg HALT}$ must be undecidable. This demonstrates a reduction from $HALT$ to $L_{\neg HALT}$'s complement, showing that if $L_{\neg HALT}$ were decidable, $HALT$ would also be, which is false. (More formally, $HALT \le_m \overline{L_{\neg HALT}}$).

:::question type="MCQ" question="Given that problem $A$ is undecidable and there is a computable function $f$ that transforms any instance of $A$ into an instance of problem $B$ such that $x \in A \iff f(x) \in B$. What can be concluded about problem $B$?" options=["Problem $B$ is decidable.","Problem $B$ is also undecidable.","Problem $B$ is finite.","Problem $B$ is always easier to solve than problem $A$."] answer="Problem $B$ is also undecidable." hint="If a solution for $B$ existed, it could be used to solve $A$, contradicting $A$'s undecidability." solution="If problem $A$ is undecidable and $A \le_m B$ (meaning $A$ is many-one reducible to $B$), then $B$ must also be undecidable. If $B$ were decidable, we could use its decider to decide $A$ by first applying the reduction function $f$ and then feeding the result to $B$'s decider. This would mean $A$ is decidable, which contradicts our premise that $A$ is undecidable. Therefore, $B$ must be undecidable."
:::

---

7. Rice's Theorem

Rice's Theorem is a powerful result in computability theory that states that any non-trivial property of the language recognized by a Turing Machine is undecidable. A property is non-trivial if it is true for some recursively enumerable languages but false for others. It is a property of the language, not of the TM's implementation.

Worked Example: Proving that the property of a TM recognizing a regular language is undecidable.

Step 1: Define the property $P$

Let $P$ be the property: "The language recognized by TM $M$, $L(M)$, is a regular language."

>

Step 2: Check if $P$ is a property of the language

The property "being regular" depends only on the language $L(M)$, not on the specific Turing Machine $M$ that recognizes it. If two different TMs recognize the same language, they either both have this property or both don't.

>

Step 3: Check if $P$ is non-trivial

>

Answer: Since $P$ is a non-trivial property of the language recognized by a Turing Machine, by Rice's Theorem, the problem of determining if $L(M)$ is regular is undecidable.

:::question type="MCQ" question="According to Rice's Theorem, which of the following properties of a Turing Machine's language is undecidable?" options=["Is $L(M)$ finite?","Does $M$ halt on the empty string?","Is $L(M)$ empty?","Does $M$ have exactly 5 states?"] answer="Is $L(M)$ empty?" hint="Rice's Theorem applies to properties of the language recognized by the TM, not properties of the TM itself. Also, the property must be non-trivial." solution="Rice's Theorem states that any non-trivial property of the language recognized by a Turing Machine is undecidable.

The question asks for an undecidable property according to Rice's Theorem. Both 'Is $L(M)$ finite?' and 'Is $L(M)$ empty?' fit this. Let's re-evaluate the options. Usually, Rice's theorem is used to show properties like emptiness, finiteness, regularity, context-freeness, etc., are undecidable.

Given the common examples, 'Is $L(M)$ empty?' (also known as $E_{TM}$) is a classic example of an undecidable problem proven by reduction from $HALT$, and also directly falls under Rice's Theorem as a non-trivial property of the language. It is true for $\emptyset$ and false for any non-empty language.

So, 'Is $L(M)$ empty?' is a correct answer according to Rice's Theorem. (Note: 'Is $L(M)$ finite?' is also undecidable by Rice's Theorem, but often one typical example is expected.)"
:::

---

8. Post Correspondence Problem (PCP)

The Post Correspondence Problem (PCP) is an undecidable decision problem that asks whether a given list of pairs of non-empty strings has a "match." A match is a sequence of indices such that concatenating the strings from the first component of the pairs in that sequence results in the same string as concatenating the strings from the second component.

Worked Example: Determine if a match exists for the following instance of PCP.

Let $P = \{ (ab, abb), (b, ba), (bba, aa) \}$.

Step 1: Try combinations of indices

We need to find a sequence of indices $i_1, i_2, \ldots, i_m$ such that $u_{i_1} \cdots u_{i_m} = v_{i_1} \cdots v_{i_m}$.

>

Step 2: Start with a single pair

* If we start with index 1: $u_1 = ab$, $v_1 = abb$. $v_1$ is longer. We need to add more strings to $u$ to catch up.
* If we start with index 2: $u_2 = b$, $v_2 = ba$. $v_2$ is longer.
* If we start with index 3: $u_3 = bba$, $v_3 = aa$. $u_3$ is longer.

Step 3: Try a sequence of indices

Let's try sequence (1, 2):
$u_1 u_2 = (ab)(b) = abb$
$v_1 v_2 = (abb)(ba) = abbba$
No match.

Let's try sequence (3, 1):
$u_3 u_1 = (bba)(ab) = bbaab$
$v_3 v_1 = (aa)(abb) = aaabb$
No match.

Let's try sequence (1, 3):
$u_1 u_3 = (ab)(bba) = abbba$
$v_1 v_3 = (abb)(aa) = abbaa$
No match.

Consider sequence (1, 2, 1):
$u_1 u_2 u_1 = (ab)(b)(ab) = abbab$
$v_1 v_2 v_1 = (abb)(ba)(abb) = abbbabb$
No match.

Consider sequence (2, 1):
$u_2 u_1 = (b)(ab) = bab$
$v_2 v_1 = (ba)(abb) = baabb$
No match.

Consider sequence (3, 2):
$u_3 u_2 = (bba)(b) = bbab$
$v_3 v_2 = (aa)(ba) = aaba$
No match.

Step 4: A systematic search (often required for actual solutions)

Let's try to build a match:
Start with (1): $u=ab, v=abb$. Need to add to $u$.
Next, choose a pair where $u_i$ starts with 'b' to match $v$'s next char. Pair 2: $(b, ba)$.
Sequence (1, 2): $u = abb$, $v = abbba$. Need to add to $u$.
Next, choose a pair where $u_i$ starts with 'b'. Pair 2 again: $(b, ba)$.
Sequence (1, 2, 2): $u = abbb$, $v = abbbaba$. Need to add to $u$.
This is getting longer for $v$ side.

Let's rethink. We want to balance lengths.
If $u_i$ is shorter than $v_i$, we pick it to make $u$ longer.
If $u_i$ is longer than $v_i$, we pick it to make $v$ longer.

Consider $P = \{ (1: ab, abb), (2: b, ba) \}$.
Try (1): $u=ab, v=abb$. $v$ is longer.
Need to add to $u$. The current string on $v$ is `abb`. The suffix `b` needs to be matched.
If we append (2):
$u_{new} = u_1 u_2 = ab \cdot b = abb$
$v_{new} = v_1 v_2 = abb \cdot ba = abbba$
Now $v$ is much longer.

Let's try sequence (2, 1):
$u_2 u_1 = b \cdot ab = bab$
$v_2 v_1 = ba \cdot abb = baabb$
No match.

Let's try sequence (1, 3):
$u_1 u_3 = ab \cdot bba = abbba$
$v_1 v_3 = abb \cdot aa = abbaa$
No match.

The given example $P = \{ (ab, abb), (b, ba), (bba, aa) \}$ actually does not have a match. This is a common situation for undecidable problems: finding a match can be hard, and proving no match exists is even harder (and generally undecidable). For a worked example, it's better to show one with a match or clearly state it's undecidable.

Let's use a simpler example that does have a match.
Let $P = \{ (0, 00), (10, 0), (011, 11) \}$.

Step 1: Try combinations

* (1): $u=0, v=00$. $v$ is longer.
* (2): $u=10, v=0$. $u$ is longer.
* (3): $u=011, v=11$. $u$ is longer.

Step 2: Try to balance lengths

If we start with (1): $u=0, v=00$. We need to make $u$ longer.
Current $v$ ends with '0'. Next $u_i$ needs to start with '0'.
Try (1, 3):
$u_1 u_3 = 0 \cdot 011 = 0011$
$v_1 v_3 = 00 \cdot 11 = 0011$
We found a match! The sequence is (1, 3).

Answer: A match exists for $P = \{ (0, 00), (10, 0), (011, 11) \}$ with the sequence of indices (1, 3).

:::question type="MCQ" question="Which of the following statements about the Post Correspondence Problem (PCP) is true?" options=["PCP is decidable for instances with only two pairs of strings.","PCP is undecidable in its general form.","PCP can always be solved by a finite automaton.","PCP is decidable if all strings are of equal length."] answer="PCP is undecidable in its general form." hint="PCP is a classic example of an undecidable problem, often used in reductions." solution="The Post Correspondence Problem (PCP) is famously undecidable in its general form. This means there is no algorithm that can determine for all possible instances of PCP whether a match exists or not. While specific restricted versions of PCP might be decidable, the general problem is not."
:::

---

9. Recursive and Recursively Enumerable Languages

Languages can be classified based on the capabilities of Turing Machines. A language is recursively enumerable (RE) if there exists a Turing Machine that accepts all strings in the language and either rejects or loops forever for strings not in the language. A language is recursive (or decidable) if there exists a Turing Machine that halts on all inputs, accepting strings in the language and rejecting strings not in the language.

Worked Example: Distinguishing between recursive and RE languages.

Consider the language $L_1 = \{ a^n b^n \mid n \ge 0 \}$ and $L_2 = HALT = \{ \langle M, w \rangle \mid M \text{ halts on input } w \}$.

Step 1: Analyze $L_1 = \{ a^n b^n \mid n \ge 0 \}$

For any string $x$, we can construct a TM that checks if $x$ is of the form $a^n b^n$.

>

Step 2: Analyze $L_2 = HALT$

For $HALT$, we know from the Halting Problem that no Turing Machine can decide it (i.e., halt on all inputs and give a correct yes/no answer). However, we can construct a TM that recognizes $HALT$:

>

Answer: $L_1$ is a recursive language because a TM can always decide its membership. $L_2$ (HALT) is a recursively enumerable language because a TM can recognize it (accept if in $HALT$, but loop if not in $HALT$), but it is not recursive because no TM can decide it.

:::question type="MCQ" question="Which of the following statements correctly characterizes the relationship between recursive and recursively enumerable languages?" options=["All recursively enumerable languages are also recursive.","All recursive languages are also recursively enumerable.","Recursive languages are a proper superset of recursively enumerable languages.","Recursively enumerable languages are always context-free."] answer="All recursive languages are also recursively enumerable." hint="Consider the definitions: a decider TM is also a recognizer TM." solution="By definition, a recursive language has a Turing Machine that halts on all inputs, accepting if the string is in the language and rejecting otherwise. Such a TM is also a recognizer (it accepts strings in the language). Therefore, all recursive languages are also recursively enumerable. However, not all recursively enumerable languages are recursive (e.g., the Halting Problem language is RE but not recursive)."
:::

---

10. Properties of Recursive and RE Languages

Recursive and Recursively Enumerable languages have specific closure properties under set operations like union, intersection, concatenation, Kleene star, and complementation. These properties are important for constructing new languages from existing ones and understanding their classification.

Worked Example: Proving that the union of two RE languages is also RE.

Step 1: Define two RE languages and their recognizers

Let $L_1$ and $L_2$ be two recursively enumerable languages. By definition, there exist Turing Machines $M_1$ that recognizes $L_1$ and $M_2$ that recognizes $L_2$.

>

Step 2: Construct a TM $M_{union}$ for $L_1 \cup L_2$

We want to build a TM $M_{union}$ that recognizes $L_1 \cup L_2$. For an input $w$:

>

Step 3: Analyze $M_{union}$'s behavior

If $w \in L_1$, $M_1$ will eventually accept. Since $M_1$ is simulated in an interleaved fashion, $M_{union}$ will eventually detect $M_1$'s acceptance and accept $w$.
If $w \in L_2$, $M_2$ will eventually accept. $M_{union}$ will detect $M_2$'s acceptance and accept $w$.
If $w \in L_1 \cup L_2$, then $w$ is in at least one of $L_1$ or $L_2$, so $M_{union}$ will eventually accept.
If $w \notin L_1 \cup L_2$, then neither $M_1$ nor $M_2$ will accept $w$. Both might loop or reject. In this case, $M_{union}$ will also loop or reject.

>

Answer: Since $M_{union}$ recognizes $L_1 \cup L_2$, the union of two RE languages is recursively enumerable.

:::question type="MCQ" question="Which of the following operations is NOT closed for recursively enumerable languages?" options=["Union","Intersection","Concatenation","Complementation"] answer="Complementation" hint="Consider the relationship between RE languages and recursive languages, especially regarding decidability." solution="Recursively enumerable (RE) languages are closed under union, intersection, and concatenation. However, they are NOT closed under complementation. The complement of an RE language is not necessarily RE. For example, $HALT$ is RE, but its complement $L_{\neg HALT}$ (the set of $\langle M, w \rangle$ where $M$ does not halt on $w$) is not RE. If both an RE language and its complement were RE, then the language would be recursive (decidable)."
:::

---

Advanced Applications

Worked Example: Using reduction and Rice's Theorem to prove undecidability.

Prove that the language $L_{FINITE} = \{ \langle M \rangle \mid L(M) \text{ is a finite language} \}$ is undecidable.

Step 1: Apply Rice's Theorem

We need to check if $L_{FINITE}$ represents a non-trivial property of the language recognized by a Turing Machine.

>

Step 2: Conclusion from Rice's Theorem

Since $L_{FINITE}$ represents a non-trivial property of RE languages, by Rice's Theorem, $L_{FINITE}$ is undecidable.

Answer: The language $L_{FINITE}$ is undecidable because it corresponds to a non-trivial property of recursively enumerable languages, making it directly subject to Rice's Theorem.

:::question type="NAT" question="Consider the language $L_{EMPTY} = \{ \langle M \rangle \mid L(M) = \emptyset \}$. If $L_{EMPTY}$ is undecidable, what is the minimum number of distinct, non-trivial properties of RE languages that are known to be undecidable, including $L_{EMPTY}$ itself, that can be directly derived from Rice's Theorem?" answer="1" hint="Rice's Theorem itself guarantees the undecidability of any non-trivial property. The question asks for the minimum number of distinct properties. If $L_{EMPTY}$ is one such property, that counts as one." solution="Rice's Theorem states that any non-trivial property of the language recognized by a Turing Machine is undecidable. $L_{EMPTY}$ is one such non-trivial property (it's true for the TM that accepts no strings, false for the TM that accepts at least one string). Therefore, at least one such property (namely, $L_{EMPTY}$ itself) is known to be undecidable. The question asks for the minimum number of distinct properties, and $L_{EMPTY}$ is one distinct property. The answer is 1."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Which of the following problems is decidable?" options=["Determining if $L(M)$ contains at least 5 strings, for a given TM $M$.","Determining if a given Turing Machine $M$ halts on all inputs.","Determining if a given regular expression $R$ generates a finite language.","Determining if $L(M_1) \cap L(M_2) = \emptyset$ for two TMs $M_1, M_2$."] answer="Determining if a given regular expression $R$ generates a finite language." hint="Decidable problems have algorithms that always halt and give a correct answer. Consider the properties of different language classes." solution="1. 'Determining if $L(M)$ contains at least 5 strings' is a non-trivial property of the language, hence undecidable by Rice's Theorem.

:::question type="NAT" question="Consider a language $L = \{ \langle M \rangle \mid M \text{ accepts } \epsilon \}$. Is $L$ decidable or undecidable? If undecidable, how many distinct, known undecidable problems (including $L$ itself, if applicable) can be cited as direct evidence, assuming it is proven via reduction from $HALT$ or $L_u$?" answer="1" hint="The problem asks about the acceptance of a specific string by a TM. This is a property of the TM's behavior, not just its language, but it can still be undecidable." solution="The language $L = \{ \langle M \rangle \mid M \text{ accepts } \epsilon \}$ is undecidable. This is a specific instance of the acceptance problem for Turing Machines, $A_{TM} = \{ \langle M, w \rangle \mid M \text{ accepts } w \}$, which is known to be undecidable. $L$ is a special case of $A_{TM}$ where $w = \epsilon$.
To prove $A_{TM}$ (and thus $L$) is undecidable, we typically reduce the Halting Problem ($HALT$) to it. This means $HALT \le_m A_{TM}$. The problem asks for the number of distinct, known undecidable problems that can be cited as direct evidence if proven via reduction from $HALT$ or $L_u$. In this case, $HALT$ (or $L_u$) is the single direct known undecidable problem used for the reduction. So the answer is 1."
:::

:::question type="MSQ" question="Select ALL true statements regarding noncomputable functions." options=["A noncomputable function cannot be computed by any Turing Machine.","The domain of a noncomputable function is always infinite.","The Halting Problem is an example of a noncomputable function (when formulated as a decision problem).","Noncomputable functions are those that require infinite time to compute for any input."] answer="A noncomputable function cannot be computed by any Turing Machine.,The Halting Problem is an example of a noncomputable function (when formulated as a decision problem)." hint="Recall the definition of a noncomputable function and the nature of the Halting Problem." solution="1. A noncomputable function cannot be computed by any Turing Machine. This is the definition of a noncomputable function. (Correct)

:::question type="MCQ" question="Given an instance of the Post Correspondence Problem (PCP) $P = \{ (0, 01), (1, 01), (10, 0) \}$. Does a match exist?" options=["Yes, using sequence (1, 2)","Yes, using sequence (3, 1)","No, a match does not exist.","Yes, using sequence (1, 3)"] answer="Yes, using sequence (1, 3)" hint="Try concatenating sequences of $u_i$ and $v_i$ to find a match." solution="Let the pairs be:

Let's test the options:

• (1, 2):

• (3, 1):

• (1, 3):

Therefore, a match exists using sequence (1, 3)."
:::

:::question type="MCQ" question="Which of the following is an example of a partial computable function that is not total computable?" options=["The function $f(n) = n+1$ for $n \in \mathbb{N}$.","The function that returns the $n$-th prime number.","The function $f(\langle M, w \rangle)$ that returns 1 if TM $M$ halts on $w$, and is undefined otherwise.","The function $f(x) = \sin(x)$ for $x \in \mathbb{R}$. "] answer="The function $f(\langle M, w \rangle)$ that returns 1 if TM $M$ halts on $w$, and is undefined otherwise." hint="A partial computable function may not be defined for all inputs in its theoretical domain, meaning the TM may not halt for those inputs." solution="1. $f(n) = n+1$ is a total computable function, defined for all natural numbers.

---

Summary

---

What's Next?

---

---

Part 2: Basics of Decidability

This section covers fundamental concepts of decidability, undecidability, and reducibility, crucial for understanding the limits of computation in CMI exams.

---

Core Concepts

1. Decidable Languages

A language is decidable if some Turing machine (TM) decides it. A TM decides a language if it halts on all inputs and accepts all strings in the language while rejecting all strings not in the language.

Worked Example: Demonstrating $A_{\text{DFA}}$ is Decidable.

The language $A_{\text{DFA}} = \{ \langle B, w \rangle \mid B \text{ is a DFA that accepts } w \}$ is decidable. We construct a TM $M$ that decides $A_{\text{DFA}}$.

Step 1: Input validation

> $M$ receives input $\langle B, w \rangle$. It first checks if $B$ is a valid encoding of a DFA and $w$ is a valid string over the alphabet of $B$. If not, $M$ rejects.

Step 2: Simulate the DFA

> $M$ simulates $B$ on input $w$. $M$ keeps track of $B$'s current state and current position in $w$.

Step 3: Process transitions

> For each symbol in $w$, $M$ updates $B$'s current state according to $B$'s transition function.

Step 4: Determine acceptance

> After processing all symbols in $w$, if $B$'s current state is an accept state, $M$ accepts. Otherwise, $M$ rejects.

Answer: $M$ always halts because a DFA processes each symbol in $w$ exactly once and has a finite number of states. Thus, $A_{\text{DFA}}$ is decidable.

:::question type="MCQ" question="Which of the following languages is decidable?" options=["$HALT_{\text{TM}} = \{ \langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w \}$","$EQ_{\text{TM}} = \{ \langle M_1, M_2 \rangle \mid M_1 \text{ and } M_2 \text{ are TMs and } L(M_1) = L(M_2) \}$","$A_{\text{CFG}} = \{ \langle G, w \rangle \mid G \text{ is a CFG that generates } w \}$","$ALL_{\text{CFG}} = \{ \langle G \rangle \mid G \text{ is a CFG and } L(G) = \Sigma^* \}$"] answer="$A_{\text{CFG}} = \{ \langle G, w \rangle \mid G \text{ is a CFG that generates } w \}$" hint="Consider the properties of Turing machines that can simulate the given formalisms." solution="Step 1: Analyze $HALT_{\text{TM}}$ and $EQ_{\text{TM}}$.
> These are known to be undecidable problems concerning the behavior of Turing machines.

Step 2: Analyze $ALL_{\text{CFG}}$.
> $ALL_{\text{CFG}}$ is undecidable. There is no algorithm to check if a CFG generates all possible strings.

Step 3: Analyze $A_{\text{CFG}}$.
> For $A_{\text{CFG}}$, we can construct a TM that decides it. The TM takes $\langle G, w \rangle$ as input. It converts $G$ into Chomsky Normal Form. Then, it uses the CYK algorithm (or a similar dynamic programming approach) to determine if $w$ can be derived from $G$. The CYK algorithm takes $\mathcal{O}(n^3)$ time, where $n$ is the length of $w$, and always halts.

Answer: $A_{\text{CFG}}$ is decidable. The other options represent known undecidable languages."
:::

---

2. Undecidable Languages

A language is undecidable if no Turing machine decides it. The concept of undecidability establishes fundamental limits on what problems can be solved algorithmically.