Computability
, , , … is a standard enumeration of all TMs with binary input.
We’ve agreed on a binary encoding #(M) ∈{0, 1}* of each TM M: The is the TM whose binary expansion of n.
A universal TM u has the property that u(#(M), x) simulates M(x). use a string pairing function like
The partial function computed by a Turing machine M is the partial function
F: ⊆ {0, 1}* {0, 1}*
defined as follows
dom f = { x∈{0, 1}* | M(x) halts}
for x∈domf,(x) is longest contiguous binary string lying to the right of the when M(x) halts.
Setting = , , , …… is a standard enumeration of all partial computable functions.
“ i is a program that computes ”
Setting = L(), , , , …… is a standard enumeration of all c.e. languages ∈{0,1}*.
Decidability, computability, and computable enumerability are defined on other domains by binary coding. Thus it makes sense to talk about sets A ⊆ N, B ⊆ N x N, etc., being decidable(or not )or c.e.(or not), and it makes sense to talk about partial functions f: ⊆NN(which might be total) being computable or not.
Define the rapidly growing faction G: NN by
{| 0}
G(n) = 1+max {| 0}
{| — is defined (halts)}
(3) means does not halt on 3
Observation1. G: NN is total, i.e., G(n) is defined for all n∈N
Observation2. G is nondecreasing, i.e., G(n+1) G(n) holds for all n.
Def. The halting problem is the set
H = {(k,)∈ NxN || }
Obsercation3. If it is decidable, G is computable.
Lemma4. G grows faster than any computable function. That is, for every computable function f:NN, we have
G(n) > f(n)
For all but finitely many n∈N.
Corollary5. G is not computable.
Theorem6 (Turing 1936). H is not decidable.
Let DEC, CE, and coCE be the classes of languages with these three properties, respectively.
Note:
DEC ⊆ CE
coDEC = DEC
DEC ⊆ coCE
Claim: DEC = CE coCE. Proof: ……
Observation7. H is c.e.
Proof: using a universal TM, we can construct a TM M such that
acc if
run forever otherwise.
Corollary8. H is not co-c.e.
Proof: immediate from the facts that H is c.e., H is not decidable, and CE coCE = DEC
Def. Let A,B ⊆ {0, 1}*. A many-one reduction (or , or m-reduction) of A to B is a computable function f: {0, 1}*{0, 1}* such that, for all x ∈ {0, 1}*,
x ∈ A f(x) ∈ B
Def. Let A,B ⊆ {0, 1}*. We say that A is to B, and we write A B, if there exists a f of A to B.
Observation9. is a reflexive, transive relation on the set of all languages.
Observation10. If AB ∈ DEC, then A∈DEC.
Proof: Assume the hypothesis. Then there exist a computable function f: {0, 1}*{0, 1}* and a TM decides B. Since f is computable, there is a TM that computes it. Then the TM that does the following decides A.
acc
x
rej
Observation11. If AB∈ CE, then A∈ CE
acc iff f(x_∈ B
x
rej or run forever other wise
Observation12. Same for coCE
Def. Let A,B ⊆ {0, 1}*. We say that A and B are many-one equivalent, and we write AB, if
AB and BA
Note that is an equivalence relation, i.e., it is reflexive, symmetric, and transitive (recall that is reflexive and transitive. The relation “inherits” these properties, and forces symmetry
Equivalence classes of are called
Definition. Let A⊆ {0, 1}* be a language, and let C be a class of languages.
• A is for C if , for every B∈C, BA.
• A is for C if A is for C and A∈C
Theorem14. H is for CE.
Proof: By Observation 7, it suffices to show that it is for CE. For this, let A ∈ CE. It suffices to show that AH. Since A ∈ CE, there is a TM M such that L(m) = A. Define
k : {0, 1}*N
k(x) = the index of a TM that ignores its input, simulates M(x), and halts if and only if accepts x.
Then k is computable, so the function f: {0, 1}*NxN. f(x) = ( (k(x),3 ) is also computable, for all x∈ {0, 1}*, x∈A M accepts C
(k(x). 3) ∈ H
f(x) ∈ H so AH via f.
Def. The diagonal halting problem is the set
K = {k∈N | (k)}
Intuition. The halting problem H={(k,l) ∈ NxN | (k)} is an infinite, 2-dimensimal boolen matrix.
Theorem15. KH. Here K is for CE.
Proof:It is clear that K is c.e., where KH holds by theorem14. Hence it suffices to prove that HK
Rice’s Theorem
Recall: : ⊆ N—>N is the partial function computed by the TM M, and that we write = for each i∈N, so that , … is the standard enumeration of all computable partial function :⊆NN
Def. An input/output(I/O) property is a set J⊆N such that, for all i,j ∈ N,
= [i∈J j∈J]
Note: Here are regarding i, j to be “equivalent” if = , and the above definition just says that J respects this equivalence relation.
Example (In each, we write θ(i) for {i∈N | })
I/O properties Non-I/O properties
halts m all inputs has an even number of states
dom is finite (3) never moves its tape head more than 99 cells from its starting position
satisfy def don’t satisfy def
Def. An I/O property J of TMs is trivial if J = Ø or J = N. Otherwise, J is nontrivial.
Rice Theorem (1951). Every nontrivial property of TMs is undecidable. In fact, every such property is for CE or for co-CE.
Proof: Let J⊆N be a nontrivial I/P property of TMs. Let m be an index of a that runs forever on all inputs, so that dom = Ø. We have two cases. 1. m∈J. Then fix i∈N-J. Define f: NN by f(n) = an index of TM a TM that, on input k, simulates and, if this halts, simulate (k). Then f is computable, and for all n∈N, n∈K = f(n)∉J and n∉Kf(n)∈J, so J via f, so J is for co-CE. 2. m∉J. Then fix j∈J, Define f: NN by f(n) = an index of a TM… then f is computable, and, for n∈K = f(n) ∉ J, so KJ via f, so J is for CE.
Algorithmic-information-theory
Algorithmic-information-theory (a.k.a., Kolmogorov complexity)
How much information is in an n-bit string?
Def. Let M be a TM, and let x∈{0, 1}*. The (plain) Kolmogorov complexity of x with respect to M is
∈{0,1}* and M(π) = x}, where min Ø = ∞
A⊆B minAminB
Intuition. If M(π)=x, then π is a description of, or program for, x in the language M
is the algorithmic information content of x with respect to M.
Def. A TM u is optimal if, for every TM M, there is a constant N such that, for every x∈{0, 1}*, c is lower case
c——Upper case upper lower
Theorem 1(optimality theorem). Every universal TM is optimal
Proof: ……
Def. The Kolmogorov complexity of a string x∈{0, 1}* is
=
Theorem2 (Optimality Theorem). For every TM M there is an optimality constant N such that , for all x∈{0, 1}*, C(x) +
Theorem3. There is a constant a∈N such that, for all x∈{0, 1}*, C(x) |x| + a
Corollary4. For all x∈{0, 1}*, C(x)< ∞
Theorem5. Let n,r ∈N. If we choose x∈{0, 1}* uniformly at random, then
Prob[C(x) n-r] > 1-
Example. n=, r = 10.
|x| = Pr[C(x) > – 10]>1-
>99.9%
Summary of theorems 3 and 5: C(x) is never much larger than, and seldom much smaller than, |x|
Corollary6. For every n∈N, there exists x∈{0, 1}* such that C(x) |x|.
Theorem7. (conservation of information). For every computable partial function f: ⊆{0, 1}*{0, 1}*, there is a constant ∈N such that, for every x ∈ dom f,
C(f(x)) C(x) +
Observation8. There is a constant a∈N such that, for all n∈N, C(n)log(n+1)+a
Corollary9. For every computable partial function f ⊆{0, 1}* there is a constant ∈N such that, for every n ∈dom f, C(f(n)) log(n+1) +
Observation10. (Sn) = ∞. That is , for every m∈N, the condition
C(x) > m
holds for all but finitely many x∈{0,1}*
Theorem11. The Kolmogorov complexity function C is not computable. In fact, if f: ⊆{0, 1}*N is any computable partial function that is a lower bound of C on its domain (i.e, f(x)c(x) for all x∈dom f, then f is bounded (i.e., there is a constant m∈N such that f(x)m holds for all x∈dom f.