Analyzing Undecidable Problems in Computation Theory

In the realm of computer science, particularly in the theory of computation, problems are classified as either decidable or undecidable. A problem is said to be decidable if there exists an algorithm (a Turing Machine that halts on all inputs) that can determine the answer (yes or no) for any instance of the problem. Conversely, a problem is undecidable if no such algorithm exists. Let's analyze each of the given problems:

Problem (i): Whether a finite automaton halts on all inputs?

A finite automaton (FA) is a very simple model of computation. When a finite automaton processes an input string, it reads the symbols one by one and transitions between states. Since the input string is finite, the FA will always finish reading the string and reach a final state (which determines if the string is accepted or rejected). A finite automaton does not have the ability to loop indefinitely on a finite input string or perform computations that would prevent it from finishing processing the input. Therefore, a finite automaton always finishes processing any given finite input string. The question "halts on all inputs" can be interpreted as "does it always finish processing any input?". For a finite automaton, the answer is always yes.

Thus, the problem of determining whether a finite automaton halts on all inputs is decidable. An algorithm simply needs to confirm that the given machine is indeed a finite automaton (which is clear from its definition); if it is, the answer is yes.

Problem (ii): Whether a given Context Free Language is Regular?

Context Free Languages (CFLs) are a class of languages that are more powerful than Regular Languages. Every regular language is also a context-free language, but the reverse is not true (e.g., $\text{L} = \{a^n b^n \mid n \ge 0\}$ is CFL but not regular). The question asks if, given a description of a Context Free Language (like a Context Free Grammar or a Pushdown Automaton), there is an algorithm to determine if this language is also a Regular Language.

This problem is a classic example of an undecidable problem in formal language theory. There is no general algorithm that can take any Context Free Grammar or Pushdown Automaton and definitively tell you whether the language it generates is regular or not.

Problem (iii): Whether a Turing Machine computes the product of two numbers?

A Turing Machine (TM) is a universal model of computation. The Halting Problem for Turing Machines (determining if a given TM halts on a given input) is famously undecidable. Problem (iii) is asking about the specific function that a Turing Machine computes. Given a Turing Machine, can we determine if it computes the multiplication function for all valid inputs?

This problem falls into the category of problems asking about the non-trivial functional behavior of a Turing Machine. According to Rice's Theorem (which states that any non-trivial property of the language accepted by a Turing Machine is undecidable), properties about the function computed by a Turing Machine are generally undecidable. Determining whether a TM computes the product of two numbers is a non-trivial property of the function it computes.

Therefore, the problem of determining whether a Turing Machine computes the product of two numbers is undecidable.

Summary of Decidability

Let's summarize the decidability of each problem:

Based on this analysis, problems (ii) and (iii) are undecidable, while problem (i) is decidable.

Conclusion on Undecidable Problems

From our analysis:

• Problem (i) concerning finite automaton halting is Decidable.
• Problem (ii) concerning whether a Context Free Language is Regular is Undecidable.
• Problem (iii) concerning whether a Turing Machine computes the product of two numbers is Undecidable.

Therefore, only problems (ii) and (iii) are undecidable.

Revision Table: Key Concepts in Computability

Additional Information: Further Exploration of Undecidability

Understanding decidability is central to the theory of computation. Here are some additional points:

• The Halting Problem for Turing Machines is the foundational undecidable problem. Many other problems are proven undecidable by reducing the Halting Problem to them.
• While determining if a CFL is regular is undecidable, many other properties of CFLs ARE decidable, such as emptiness, finiteness, and membership.
• Properties of recursive languages (languages accepted by Turing Machines that always halt) are often decidable, while properties of recursively enumerable languages (languages accepted by Turing Machines that may not halt on non-accepted inputs) are often undecidable.
• Problems about the equivalence of computational models are often undecidable when the models are powerful (like Turing Machines), but decidable for weaker models (like Finite Automata). For instance, equivalence of two FAs is decidable, but equivalence of two TMs is undecidable.