patternMinor
Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable
Viewed 0 times
showthewhoselengththanrecursivelyenumerablekolmorgorovthatsmaller
Problem
Define the language
$\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$
where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$.
Prove that $R$ is co-recursively enumerable (co-r.e.).
So far, I have the following:
In order to prove the above, we need to show
$\qquad R^c$ = $\{x \in \{0,1\}^\ast \mid C(x) \lt |x| \}$
is r.e. That is there exists a program $\pi$ such that the univeral TM $U$ with argument $\pi$ equals $x$ and $|\pi| \lt |x|$ (where $U(\pi) = x$ and $|\pi| \lt |x|$).
We start by enumerating all strings in $\{0,1\}^\ast$.
I have no idea where to go from this point onward.
$\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$
where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$.
Prove that $R$ is co-recursively enumerable (co-r.e.).
So far, I have the following:
In order to prove the above, we need to show
$\qquad R^c$ = $\{x \in \{0,1\}^\ast \mid C(x) \lt |x| \}$
is r.e. That is there exists a program $\pi$ such that the univeral TM $U$ with argument $\pi$ equals $x$ and $|\pi| \lt |x|$ (where $U(\pi) = x$ and $|\pi| \lt |x|$).
We start by enumerating all strings in $\{0,1\}^\ast$.
I have no idea where to go from this point onward.
Solution
Fancy answer
We need to show that the set
$$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$
is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to
$$\exists n, m \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$
where $T$ is Kleene's predicate and $U$ the associated output function.
In words, the formula means: there exists a code $n$ such that the $n$-th machine computes $x$ (on input $0$) and the length of $n$ is less than the length of $x$. We are done because (1) is a $\Sigma^0_1$-formula, therefore it defines a c.e. predicate.
Scholium: a $\Sigma^0_1$ formula is a formula of the form
$$\exists n \in \mathbb{N} \,.\, \phi(n, x)$$
where $\phi(n,x)$ is a decidable formula. Such a formula determines a c.e. predicate: to semidecide whether it holds for $x$, just run a loop $n = 0, 1, 2, \ldots$ and test for each $n$ whether $\phi(n,x)$ holds. If and when such an $n$ is found, terminate.
Non-fancy answer
In paralell, run all machines described by codes of length less than $|x|$ (there are around $2^{|x|}$ such machines, which is a finite number). If and when one of them stops and produces output $x$, terminate.
We need to show that the set
$$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$
is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to
$$\exists n, m \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$
where $T$ is Kleene's predicate and $U$ the associated output function.
In words, the formula means: there exists a code $n$ such that the $n$-th machine computes $x$ (on input $0$) and the length of $n$ is less than the length of $x$. We are done because (1) is a $\Sigma^0_1$-formula, therefore it defines a c.e. predicate.
Scholium: a $\Sigma^0_1$ formula is a formula of the form
$$\exists n \in \mathbb{N} \,.\, \phi(n, x)$$
where $\phi(n,x)$ is a decidable formula. Such a formula determines a c.e. predicate: to semidecide whether it holds for $x$, just run a loop $n = 0, 1, 2, \ldots$ and test for each $n$ whether $\phi(n,x)$ holds. If and when such an $n$ is found, terminate.
Non-fancy answer
In paralell, run all machines described by codes of length less than $|x|$ (there are around $2^{|x|}$ such machines, which is a finite number). If and when one of them stops and produces output $x$, terminate.
Context
StackExchange Computer Science Q#35195, answer score: 7
Revisions (0)
No revisions yet.