# Kolmogorov Complexity and the Halting Problem

Assuming that \(U\) represents a Universal Turing Machine and \(\epsilon\) is the empty string:

\begin{equation} K_U(x) = \min_{|p|} \{p: U \circ p(\epsilon) = x\} \end{equation}

where \(x \neq x' \implies p \neq p'\) so \(K_U(\cdot)\) is injective.

## Proof that \(K_U(\cdot)\) is not a computable search procedure:

If \(K_U(\cdot)\) is computable, then we would be able to determine whether an arbitrary program \(g\) halts on the empty string \(\epsilon\), as we would be able to evaluate:

\begin{equation} U \circ g(\epsilon) \end{equation}

Furthermore, given that \(g\) is arbitrary and \(g(\epsilon)\) represents an arbitrary string we would also be able to evaluate:

\begin{equation} U \circ f \circ g(\epsilon) \end{equation}

for an arbitrary program \(f\) that composes with \(g\). It follows that we would be able to solve the halting problem. QED.