GO Classes DPP | TOC|DECIDABILITY

Answer 1

Analyzing Language $L_1$

$L_1=\{\langle M\rangle \mid M$ is a Turing Machine with an even number of states $\}$

This language asks about a property of the Turing Machine's description or encoding ( $\langle M\rangle$ ), not the language it accepts ( $L(M)$ ).

• Property: Does the TM's description list an even number of states?
   
• Decidability: This is a syntactic property. We can build a simple algorithm (another Turing Machine, let's call it $D$ ) that does the following:

1. Takes the encoding $\langle M\rangle$ as input.

2. Parses the encoding to find the section that defines the states.

3. Counts the number of states.

4. Checks if the count is even. If yes, it accepts. If no, it rejects.

• This algorithm is guaranteed to halt for any given TM encoding. Therefore, $L_1$ is decidable.

Analyzing Language $L_2$

$L_2=\{\langle M\rangle \mid M$ is a Turing Machine and the language $L(M)$ is finite $\}$

This language asks about a property of the language accepted by the TM, which is a semantic property. We can use Rice's Theorem to analyze this,

Rice's Theorem states that any non-trivial property of the language of a Turing machine is undecidable.

To apply the theorem, we need to check two conditions for the property "the language is finite":
1. Is the property non-trivial? A property is non-trivial if there is at least one Turing machine that has the property and at least one that does not.

• Yes, some TMs have the property: A TM that accepts only the string "01" has a finite language ( $L=\{01\}$ ).
   
• Yes, some TMs do not have the property: A TM that accepts all strings over $\{0,1\}^*$ has an infinite language. Since the property is non-trivial, Rice's Theorem applies.

2. Is it a property of the language? Yes, "finiteness" describes the set of strings accepted, not the structure of the TM itself.

Since both conditions are met, Rice's Theorem tells us that $L_2$ is undecidable.

Answer 2

$L_1 = \{\langle M \rangle \mid M \text{ is a Turing Machine with an even number of states}\}$

This language asks a question about a syntactic property of the Turing Machine $M$. That can be determined just by reading the instuction manual, wihout having to simulate it's behavior on any input.

We can easily build a decider for $L_1$:

1. Take the encoding $\langle M \rangle$ as input.

2. Parse the encoding to find the section that defines the set of states, $Q$.

3. Count the number of states in $Q$.

4. If the count is an even number, accept (and halt).

5. If the count is an odd number, reject (and halt).

Since this algorithm is guaranteed to halt for any input $\langle M \rangle$ and correctly determines if the number of states is even, the language $L_1$ is decidable.

 

$L_2 = \{\langle M \rangle \mid M \text{ is a Turing Machine and the language } L(M) \text{ is finite}\}$

This language asks a question about a semantic property of the Turing Machine $M$. A semantic property is one that depends on the language $L(M)$ that the machine accepts, not just its description. To know if $L(M)$ is finite, you must know about the machine's behavior on all possible inputs. 

Rice's Theorem says: Any "non-trivial" semantic property of a TM's language is UNDECIDABLE.

A "non-trivial" property means it's not true for all Turing machines, nor is it false for all Turing machines.

• TM that has the property: We can create a TM $M_{fin}$ that accepts only the string "a". $L(M_{fin}) = \{a\}$, which is finite.

• TM that does not have the property: We can create a TM $M_{inf}$ that accepts all strings ($L(M_{inf}) = \Sigma^*$). This language is infinite.

Since the property is true for some and false for others, it is non-trivial.

So, $L_2$ is undecidable.

Comments

In simple terms....

Syntactic Property: "Does this book have an even number of pages?" or "Does this book contain the word 'dragon'?" You can answer this just by inspecting the book.

Semantic Property: "Is this book a sad story?" To answer this, you must read and understand the book (i.e., run the machine).

Something worth remembering: All syntactic properties are decidable