45 Undecidability

Proposition

CNF${}^{poly}$ contains undecidable languages

Proof

Let $H\subseteq \mathbb{N}$ be the set of natural numbers coding halting Turing Machines (without inputs). Define the following sequence of CNFs:

$$A_n:=\{\begin{array}{l}{x}_1\vee \neg x_{1}n\in H\\ x_1\wedge \neg x_{1}n\notin H\end{array}$$

Note that $A_n$ evaluates to 1 on an input $\in \{0,1{\}}^n$ if an only if the $n^{th}$ Turing Machine halts. The induced language $\subseteq \{0,1{\}}^{\star }$ is clearly undecidable by reduction to H.