Understanding Decidable Problems on Turing Machines

A problem is considered decidable if there exists a Turing machine (TM) that halts on every input string and gives a YES or NO answer. These problems correspond to recursive languages. If a Turing machine can answer YES for inputs in the language but might loop forever for inputs not in the language, the problem is recursively enumerable (RE). Decidable problems are a subset of recursively enumerable problems.

Let's analyze each given problem in the context of Turing machines and their decidability status.

Analysis of Problem (a): G is a CFG with L(G) = $\varphi$

This problem asks whether the language generated by a given Context-Free Grammar (CFG) G is empty ($\varphi$).

• A CFG is defined by its set of variables, terminals, production rules, and a start symbol.
• To check if L(G) is empty, we need to determine if any terminal string can be derived from the start symbol.
• We can solve this using a marking algorithm:
  1. Mark all terminal symbols.
  2. Repeatedly mark any variable A if there is a production rule $A \to \beta_1 \beta_2 ... \beta_k$ where all symbols $\beta_i$ are already marked.
  3. Continue until no new variables can be marked.
• If the start symbol is marked at the end of this process, the language L(G) is not empty. If the start symbol is not marked, L(G) is empty.
• This algorithm terminates because the number of variables is finite.

Since we can construct a Turing machine that implements this marking algorithm and it always halts, the problem "G is a CFG with L(G) = $\varphi$" is decidable.

Analysis of Problem (b): There exist two TMs M1 and M2 such that L(M) $\subseteq$\{L(M1) $\cup$ L(M2)\} = language of all TMs

This problem statement contains confusing phrasing ("= language of all TMs"). Let's interpret the core question as checking a property about the language L(M) accepted by a given Turing machine M, specifically its relationship to languages accepted by other Turing machines M1 and M2.

• The set of languages accepted by Turing machines are the Recursively Enumerable (RE) languages.
• The union of two RE languages is also an RE language. So L(M1) $\cup$ L(M2) is an RE language.
• The problem, likely intended, is related to checking if L(M) is a subset of L(M1) $\cup$ L(M2) for some M1, M2, or whether L(M) has some structural property related to unions of RE languages.
• General problems involving the properties of languages accepted by Turing machines are often undecidable due to Rice's Theorem, which states that any non-trivial property of the language of a Turing machine is undecidable.
• Checking language inclusion (L(M) $\subseteq$ L(M')) between two arbitrary TMs is a well-known undecidable problem. Extending this to checking L(M) $\subseteq$ (L(M1) $\cup$ L(M2)) for arbitrary M1 and M2, or checking for the *existence* of such M1 and M2 with specific properties related to their languages, falls into the realm of undecidable problems concerning TM languages.

Therefore, problem (b), as stated or with plausible interpretations, is undecidable.

Analysis of Problem (c): M is a TM that accepts w using at most 2 |w| cells of tape

This problem asks about a property of the Turing machine M related to its space usage during computation. Specifically, it asks if M accepts a string w using space bounded by $2 \times (\text{length of w})$. The phrasing "M is a TM that accepts w using at most 2 |w| cells" is slightly ambiguous but can be interpreted as asking whether the language accepted by M under this specific space constraint is non-empty, or whether *all* strings in L(M) are accepted within this bound, or similar.

• Checking if a TM M accepts a specific string w within a specific space bound (like 2|w|) is decidable. You can simulate M on w and count the tape cells used. Since the number of configurations within a fixed space bound is finite, the simulation either halts (accepts or rejects) or enters a loop within that space.
• However, the problem here is a property of the TM itself, not a check for a specific string. It likely asks if there exists *any* string w accepted by M using at most 2|w| cells, or if L(M) equals the language accepted by M within this space bound, or similar.
• The set of languages accepted by Turing machines within a linear space bound (like $c \times |w|$ for some constant c) corresponds to the class of Context-Sensitive Languages (CSLs), which are accepted by Linear Bounded Automata (LBAs).
• The problem of determining if the language accepted by an LBA (or a space-bounded TM) is empty is undecidable. This is a standard result in complexity theory.
• Problem (c) is equivalent to asking if the language accepted by M when restricted to 2|w| space is non-empty, which is an undecidable problem.

Therefore, problem (c) is undecidable.

Conclusion on Decidable Problems

Based on the analysis:

• Problem (a) (emptiness for CFG) is decidable.
• Problem (b) (property of TM languages related to union) is undecidable.
• Problem (c) (existence of a string accepted within linear space bound) is undecidable.

Thus, only problem (a) is a decidable problem.

Revision Table: Core Concepts in Automata and Computability

Additional Information: Undecidability in Theory of Computation

Undecidability is a central concept in the theory of computation. It refers to problems for which no algorithm (or equivalently, no Turing machine that halts on all inputs) can exist to provide a correct YES or NO answer for all possible inputs.

Some classic examples of undecidable problems related to Turing machines include:

• The Halting Problem: Given a Turing machine M and an input string w, does M halt on w? This is famously undecidable.
• The Membership Problem for TMs: Given a Turing machine M and an input string w, is w in L(M)? This is undecidable (it is RE, but not recursive).
• The Equivalence Problem for TMs: Given two Turing machines M1 and M2, is L(M1) = L(M2)? This is undecidable.
• The Inclusion Problem for TMs: Given two Turing machines M1 and M2, is L(M1) $\subseteq$ L(M2)? This is undecidable.

Problems about properties of the *language* accepted by a TM are typically undecidable by Rice's Theorem. Problem (b) and (c) in the question touch upon properties of the TM's language or its computation resource usage, which are generally undecidable.

In contrast, many problems concerning simpler models of computation, such as Finite Automata (FA) or Context-Free Grammars (CFG), are decidable. For instance, emptiness, finiteness, and membership are decidable for both FA and CFG. Equality is decidable for FA but undecidable for CFG.