3. Computability Theory¶

Definition

A subprobability measure on $\set{0,1}^*$ is a function $p: \set{0,1}^* \ to {[0,1]}$ such that

\[\sum_{x\in\set{0,1}^*}p(x)\leq 1\]

Definition

A probability measure on $\set{0,1}^*$ is a function $p: \set{0,1} \to {[0,1]}$ such that

\[ \sum_{x\in\set{0,1}^*}p(x)= 1\]

Definition

A function $f : \{0,1\}^* \to \mathbb{R}$ is computable if there is a computable function

\[ \hat{f} : \{0,1\}^* \times \mathbb{N} \to \mathbb{Q} \]

such that, for all $x \in \{0,1\}^*$ and $r \in \mathbb{N}$,

\[ |\hat{f}(x,r) - f(x)| \;\le\; 2^{-r}. \]

The variable $r$ is called the precision parameter.

Definition

A function $f : \{0,1\}^* \to \mathbb{R}$ is upper semicomputable if there is a computable function

\[ \hat{f} : \{0,1\}^* \times \mathbb{N} \to \mathbb{Q} \]

with the following two properties:

For all $x \in \{0,1\}^*$ and $t \in \mathbb{N}$:

\[ \hat{f}(x,t) \;\le\; \hat{f}(x,t+1) \;\le\; f(x). \]
For all $x \in \{0,1\}^*$:

\[ \lim_{t \to \infty} \hat{f}(x,t) \;=\; f(x). \]

The variable $t$ is called the patience parameter.

Definition

A function $f : \{0,1\}^* \to \mathbb{R}$ is lower semicomputable if $-f$ is upper semicomputable.

Definition

A real number $\alpha \in \mathbb{R}$ is computable if the constant function$K_\alpha : \{0,1\}^* \to \mathbb{R}$

\[ K_\alpha(w) = \alpha \]

is computable.

Fix a standard enumeration $M_0, M_1, M_2, \ldots$ of all Turing machines with inputs and outputs in $\mathbb{N}$. For each $i \in \mathbb{N}$, let $\varphi_i : \mathbb{N} \to \mathbb{N}$ be the partial function computed by $M_i$.

Definition

The (diagonal) halting problem is the set

\[ K = \{\,k \in \mathbb{N} \mid M_k(k) \downarrow\}. \]

Fact

$K$ is computably enumerable but not decidable.

Definition

A property of programs is a set $P \subseteq \mathbb{N}$. We say $P$ is trivial if $P = \varnothing$ or $P = \mathbb{N}$. Otherwise, $P$ is non-trivial.

Definition

An I/O property of programs is a property $P \subseteq \mathbb{N}$ satisfying

\[ \varphi_i = \varphi_j \;\;\Longrightarrow\;\; \bigl[i \in P \iff j \in P\bigr]. \]

Rice’s Theorem

Every non-trivial I/O property is undecidable.

Definition

An enforcer of an I/O property $P$ of programs is a function $f : \mathbb{N} \to \mathbb{N}$ such that for all $i \in \mathbb{N}$:

$f(i) \in P$,
$i \in P \Longrightarrow \varphi_{f(i)} = \varphi_i.$

Definition

Let $P \subseteq \mathbb{N}$. We say $P$ is computably enforceable if there exists a computable function $f : \mathbb{N} \to \mathbb{N}$ that enforces $P$.

Definition

A prefix set is a language $A \subseteq \{0,1\}^*$ such that for all $x, y \in \{0,1\}^*$,

\[ x \sqsubseteq y \;\Longrightarrow\; x = y, \]

i.e., no element of $A$ is a prefix of any other element of $A$.

Definition

Define

\[ P_{\mathtt{pref}} = \{\,i \in \mathbb{N} \mid \textup{$\mathrm{dom}\varphi_i$ is a prefix set}\}. \]

Theorem

$P_{\mathtt{pref}}$ is computably enforceable.

(Proof: TODO.)

Since $P_{\mathtt{pref}}$ is computably enforceable, there is an enumeration of all [1] prefix Turing Machines, $\hat{M}_0, \hat{M}_1, \hat{M}_2, \ldots$. We call this the standard enumeration of all prefix TMs.

Definition

A universal prefix TM is a prefix Turing Machine $\hat{U}$ such that, for all $n \in \mathbb{N}$ and $\pi \in \{0,1\}^*$,

\[ \hat{U}(\,0^n 1 \,\pi) \;\cong\; \hat{M}_n(\pi). \]

Definition

Let $M$ be a Turing Machine.

For each $x \in \{0,1\}^*$, the set of programs for $x$ on $M$ is

\[ \mathrm{PROG}_M(x) \;=\; \{\,\pi \in \{0,1\}^* \mid M(\pi) = x\}. \]
The set of valid programs on $M$ is

\[ \mathrm{PROG}_M \;=\; \{\,\pi \in \{0,1\}^* \mid M(\pi)\!\downarrow\}. \]

Observation

For every TM $M$,

\[ \mathrm{PROG}_M \;=\; \bigcup_{x \in \{0,1\}^*} \mathrm{PROG}_M(x), \]

which is a union of disjoint sets $\mathrm{PROG}_M(x)$.

Optimality Theorem

For each prefix TM $M$, there is an optimality constant $c_M \in \mathbb{N}$ such that, for all $x \in \{0,1\}^*$,

\[ K(x) \le K_M(x) + c_M. \]