Decidability

The decidability of a decision problem or language refers to whether there exists a Turing machine that can accept the language or solution to the problem and halts every time. Informally, it means a decidable problem is one that can be answered by a yes/no.

Definition §

Decidable (Language) ^def-language

Let $A$ be a language. Then:

$$\text{A is Turing-decidable}⟺\exists \text{TM, M}\text{ s.t. }A=L(M)\wedge \text{M is a decider}$$

• $M$ is a Turing machine
• That is, $M$ accepts every string $w\in A$ and rejects every string $w\notin A$, and more importantly, always halts (definition of a decider)

Decidable (Decision Problem) ^def-problem

Let $P(\vec{x})$ be a decision problem (of arity $n$) over an input set $X=\{{\vec{x}}_1,{\vec{x}}_2,\dots {\vec{x}}_m\}$

$$\text{P is decidable}⟺\exists \text{TM, M}\text{ s.t. }L(M)=\{⟨{\vec{x}}_1,P({\vec{x}}_1)⟩,⟨{\vec{x}}_2,P({\vec{x}}_2)⟩,\dots ⟨{\vec{x}}_m,P({\vec{x}}_m)⟩\}\wedge M\text{ is a decider}$$

• $M$ is a Turing Machine
• This implies that a problem can be verifiable. Given a potential solution to the problem, $M$ can check if the solution is correct or not.
• This also means undecidable problems cannot be verified.

Side note: Connection to logic

The problem of satisfiability actually relates to Turing machines. Propositional satisfiability is decidable, meaning for any given formula, there is always a Turing machine that accepts a proposition iff it is satisfiable, and this machine always halts. Predicate satisfiability, unfortunately, is recognisable but not decidable, meaning there is a machine that recognises satisfiable predicates, but it may run forever for unsatisfiable predicates.

Closure Properties §

Just like some operations are closed for regular languages, we also have some closure properties for decidable language.

The following operations on languages preserve decidability:

• Complement
• Union
• Intersection
• Concatenation
• Kleene Star
• Set Difference (can be constructed from complement and intersections)

Theorem §

T1: The complement of a decidable language is decidable ^t1

$$\text{L is decidable}⟹\text{LC is decidable}$$

Proof $H$ for $L$, construct a new decider $H^C$, that accepts if $H$ rejects and rejects if $H$ accepts (so it does the opposite of $H$). Then, $H^C$ decides $L^C$

Relatively simple. Given a decider

T2: The union of two decidable languages is decidable ^t2

$$\text{M,N are decidable}⟹\text{M∪N is decidable}$$

Proof $H_M,H_N$ be the deciders for $M,N$ respectively. Then we can create a new decider, $S$ that simulates both deciders (since they always halt). $S$ accepts if either $H_M$ or $H_N$ accepts, and rejects otherwise. $S$ is then a decider that decides $M\cup N$

Again, very straightforward. Let

T3: The intersection of two decidable languages is decidable ^t3

$$\text{M,N are decidable}⟹\text{M∩N is decidable}$$

Proof $H_M,H_N$ be the deciders for $M,N$ respectively. Then we can create a new decider, $S$ that simulates both deciders (since they always halt). $S$ accepts if both $H_M$ and $H_N$ accept, and rejects otherwise. $S$ is then a decider that decides $M\cap N$

Super similar to the closure of the union. Let

T4: The concatenation of two decidable languages is decidable

$$\text{M,N are decidable}⟹\text{M∘N is decidable}$$

Proof $H_M$ and $H_N$. We use the fact that a non-deterministic Turing Machines are equivalent to deterministic TMs and multi-tape Turing machines are equivalent to single-tape Turing Machines. Construct a non-deterministic, two-tape Turing machine $S$ that, on input $w$:

Assume we have deciders

• Scans the input tape until it encounters a blank symbol.
• For each character read along the way, non-deterministically choose to overwrite one of the characters with a ‘marked’ version, call it $m$
• This also applies to the first blank symbol read, it can be marked as well.
• Copy every character to the left of $m$ onto the work tape.
• Then, run $H_M$ on the work tape. If it accepts, continue to the next step. Else, $S$ rejects.
• Clear out the work tape (replace every non-blank character with a blank)
• Copy the remaining characters from the input tape ($m$ and everything to the right of it) onto the work tape
• Run $H_N$ on the work tape. If it accepts, $S$ accepts

Essentially, this Turing machine tries to make a partition for every location in the word, and sees if that mark is a valid concatenation.

T5: The Kleene star of a decidable language is decidable

$$\text{L is decidable}⟹\text{L∗ is decidable}$$

Proof $H$ . We use the fact that a non-deterministic Turing Machines are equivalent to deterministic TMs and multi-tape Turing machines are equivalent to single-tape Turing Machines. Construct a non-deterministic, two-tape Turing machine $S$ that, on input $w$:

This proof is very similar to the one for concatenation. Assume we have a decider

• Scans the input tape until it encounters a blank symbol.
• For each character read along the way, non-deterministically choose to overwrite one of the characters with a ‘marked’ version, call it $m$
• This also applies to the first blank symbol read, it can be marked as well.
• Copy every character to the left of $m$ onto the work tape.
• Then, run $H$ on the work tape. If it accepts, continue to the next step. Else, $S$ rejects.
• Clear out the work tape (replace every non-blank character with a blank)
• Now scan the input tape from $m$ to the blank symbol, and again non-deterministically choose a new character to be marked as $m$
• Repeat the process until there are only blank symbols left to scan.
• $S$ accepts.