17. Decidability

Mar 1/3, 2022

Turing-acceptable

Language $L$ is Turing-acceptable if there is a TM $M$ that accepts $L$ .

Turing-acceptable == Turing-recognizable == recursively enumerable
for any input string $w$ :
- $w \in L$ then $M$ halts in accept state
- $w \notin L$ then $M$ halts in non-accept state or loops forever
For Turing-acceptable language it is possible, for some input, the machine enters an infinite loop

Decidability

Definition. A language $L$ is decidable if there is a Turing machine (decider) $M$ which accepts $L$ and halts on every input string.

Also known as recursive languages.

Decidable means there exists an algorithm that always terminates on any input.

Turing-decidable, for any input $w$ - $w \in L$ then $M$ halts in accept state - $w \notin L$ then $M$ halts in non-accept state

Observation: every decidable language is Turing-acceptable.

Sometimes it is convenient to have Turing machines with single accept or reject states:

These are the only halting states that result to possible halting configurations
We can convert any TM to have single accept and reject states (similar to NFA)
in a decider, in finite time, either accept/reject will eventually be reached

A computational problem is decidable (solvable) if the corresponding language is decidable.

Decidable Examples

Show that the following are decidable.

Example: is number $x$ prime? $L = {2, 3, 5, 7, \dots}$ .

Decider for primes: on input number $x$ , divide $x$ with all possible numbers between 2 and $\sqrt{x}$ . If any divides $x$ then reject, else accept.

The decider TM can be designed based on the algorithm.

Example: Does DFA $M$ accept the empty language $L (M) = \emptyset$ .

Corresponding language: v = { $< M >$ is a DFA that accepts empty language $\emptyset$ }. Describe $M$ as a binary string (similar to TMs).

Decider for Empty $_{D F A}$ , on input $< M >$ : determine whether the is a path from the initial state to any accept state. If path exists reject, else accept.

Example: Does DFA $M$ accept a finite language?

Corresponding language: Finite $_{D F A}$ = { $< M >$ is a DFA that accepts a finite language }.

Decider for Finite $_{D F A}$ , on input $< M >$ : check if there is a walk, with a cycle, from the initial state to an accepting state. If path exists then rejects, else accept.

Example: Does DFA $M$ accept string $w$ ?

Corresponding language: A $_{D F A}$ = { $< M, w >$ where $M$ is a DFA that accepts string $w$ }.

Decider for A $_{D F A}$ , on input $< M, w >$ : Run DFA $M$ on input string $w$ . If $M$ accepts $w$ then accept $< M, w >$ and halt. Else reject $< M, w >$ and halt.

Example: Do DFAs $M_{1}$ and $M_{2}$ accept the same language?

Corresponding language: Equal $_{D F A}$ = { $< M_{1}, M_{2} >$ where $M_{1}$ and $M_{2}$ are DFAs that accept the same language }.

Decider for Equal $_{D F A}$ , on input $< M_{1}, M_{2} >$ : Let $L_{1}$ be the language of DFA $M_{1}$ and let $L_{2}$ be the language of DFA $M_{2}$ . Construct a combination DFA $M$ such that: $L (M) = (L \cap \overset{―}{L_{2}}) \cup (\overset{―}{L) 1} \cap L_{2})$ .

Reduce the problem to emptyset problem: $(L \cap \overset{―}{L_{2}}) \cup (\overset{―}{L) 1} \cap L_{2}) = \emptyset$ , which we know how to solve.

When the machines accept the same language:

Show that $L \cap \overset{―}{L_{2}} = \emptyset$ => $L_{1} \subseteq L_{2}$
show that $\overset{―}{L_{1}} \cap L_{2} = \emptyset$ => $L_{2} \subseteq L_{1}$
Then $L_{1} = L_{2}$ .

Also show opposite:

Show that $L \cap \overset{―}{L_{2}} \neq \emptyset$ => $L_{1} ⊄ L_{2}$
show that $\overset{―}{L_{1}} \cap L_{2} \neq \emptyset$ => $L_{2} ⊄ L_{1}$
Then $L_{1} \neq L_{2}$ .

Therefore we only need to determine $L (M) = (L \cap \overset{―}{L_{2}}) \cup (\overset{―}{L) 1} \cap L_{2}) \neq \emptyset$ which is a solvable problem from DFAs Empty $_{D F A}$ .

Complement

Theorem. If language $L$ is decidable, then its complement $\overset{―}{L}$ is decidable too.

Proof: build a Turing machine $M^{'}$ that accepts $\overset{―}{L}$ that halts on every input string ( $M^{'}$ is a decider for $\overset{―}{L}$ ): take the decider for $L$ then transoform its accept state to reject state, and vice versa.

Alternative proof: build Turing machine $M^{'}$ . On each input string $w$ do: 1. Let $M$ be decider for L 2. Run $M$ witn input string $w$ and if $M$ accepts then reject. If $M$ rejects, then accept. $M^{'}$ accepts $\overset{―}{L}$ and halts on every input string.