Skip to content

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\(_{DFA}\), 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\(_{DFA}\) = { \(<M>\) is a DFA that accepts a finite language }.

Decider for Finite\(_{DFA}\), 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\(_{DFA}\) = { \(<M,w>\) where \(M\) is a DFA that accepts string \(w\) }.

Decider for A\(_{DFA}\), 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\(_{DFA}\) = { \(<M_1,M_2>\) where \(M_1\) and \(M_2\) are DFAs that accept the same language }.

Decider for Equal\(_{DFA}\), 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 \overline{L_2}) \cup (\overline{L)1} \cap L_2)\).

Reduce the problem to emptyset problem: \((L \cap \overline{L_2}) \cup (\overline{L)1} \cap L_2) = \emptyset\), which we know how to solve.

When the machines accept the same language:

  1. Show that \(L \cap \overline{L_2} = \emptyset\)   =>   \(L_1 \subseteq L_2\)
  2. show that \(\overline{L_1} \cap L_2 = \emptyset\)   =>   \(L_2 \subseteq L_1\)
  3. Then \(L_1 = L_2\).

Also show opposite:

  1. Show that \(L \cap \overline{L_2} \neq \emptyset\)   =>   \(L_1 \not\subset L_2\)
  2. show that \(\overline{L_1} \cap L_2 \neq \emptyset\)   =>   \(L_2 \not\subset L_1\)
  3. Then \(L_1 \neq L_2\).

Therefore we only need to determine \(L(M) = (L \cap \overline{L_2}) \cup (\overline{L)1} \cap L_2) \neq \emptyset\) which is a solvable problem from DFAs Empty\(_{DFA}\).

Complement

Theorem. If language \(L\) is decidable, then its complement \(\overline{L}\) is decidable too.

Proof: build a Turing machine \(M'\) that accepts \(\overline{L}\) that halts on every input string (\(M'\) is a decider for \(\overline{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 \(\overline{L}\) and halts on every input string.