Computability and Logic (5th Edition, 2007) – Solutions to
Problems (Part A & B) – Boolos
Enumerable set - answers-One whose elements can be arranged in a single list
Enumerable set (formal) - answers-A is enumerable ↔ there is f s.t. f enumerates A ↔ f is a
bijection and f; N --> A ↔ A is countable
Cardinality (of A and B) - answers-1. ||A|| = ||B|| iff there is a bijection f:A --> B 2. ||A|| ≤
||B|| iff there is an injection f:A-->B
Finite set - answers-A set is finite if it has the same cardinality as set {0,...,n} for n∈N
Countable set - answers-A set is countable iff ||A|| ≤ N0
Cantor's theorem - answers-For any set A, ||A|| < ||p(A)||
Diagonalization - answers-Mighty important method to prove a set is uncountable
Doubler Turing Machine - answers-Uses 11 states to double the input
TM-computable function - answers-f; N-->N is T-computable iff there exists M st M computes f
<> f is the k-ary function computed by M if when M starts in a standard position:
1. If f(n1,...,nk) = m, then M eventually halts in a standard position, and
2. If (fn1,...,nk) ↑, then M never halts or halts in a non-standard position
1
, Examples of TM non-computable functions - answers-1. Any function that does not map from N
to N (e.g. sin(x), sqrt(x))
2. Some functions from N to N, notably:
i) Function t (Lecture 5)
ii) Function p (Lecture 6; Busy Beaver)
iii) h(m,n) - HP function
Basic functions - answers-Zero function (z = 0); successor function (s(0)=1, s(1)=2,...); identity
function (idi(x1,...,xi,...,xn) = xi)
Primitive recursive functions - answers-The smallest class of functions satisfying the following:
1. Every basic function is primitive recursive function
2. (Composition closure) If f and g1,...,gk PR, then Cn[f, g1,...,gk)(x1,...,xn) =
f(g1(x1,...,xn),...,gk(x1,...,xn))
3. (Primitive Recursion closure) If f and g are PR, then Pr[f,g] is also PR, where:
Pr[f,g](x,0) = f(x)
Pr[f, g](x, s(y)) = g(x,y,Pr[f,g](x,y))
Recursive fuctions - answers-The smallest class of functions satisyfying:
1. Every basic function is recursive function
2. Composition closure
3. Primitive Recursion Closure
4. (Minimization Closure) If f is a recursive function, then Mn[f] is a recursive function:
Mn[f](x) = μy[f(x,y) = 0]; undefined otherwise
2
Problems (Part A & B) – Boolos
Enumerable set - answers-One whose elements can be arranged in a single list
Enumerable set (formal) - answers-A is enumerable ↔ there is f s.t. f enumerates A ↔ f is a
bijection and f; N --> A ↔ A is countable
Cardinality (of A and B) - answers-1. ||A|| = ||B|| iff there is a bijection f:A --> B 2. ||A|| ≤
||B|| iff there is an injection f:A-->B
Finite set - answers-A set is finite if it has the same cardinality as set {0,...,n} for n∈N
Countable set - answers-A set is countable iff ||A|| ≤ N0
Cantor's theorem - answers-For any set A, ||A|| < ||p(A)||
Diagonalization - answers-Mighty important method to prove a set is uncountable
Doubler Turing Machine - answers-Uses 11 states to double the input
TM-computable function - answers-f; N-->N is T-computable iff there exists M st M computes f
<> f is the k-ary function computed by M if when M starts in a standard position:
1. If f(n1,...,nk) = m, then M eventually halts in a standard position, and
2. If (fn1,...,nk) ↑, then M never halts or halts in a non-standard position
1
, Examples of TM non-computable functions - answers-1. Any function that does not map from N
to N (e.g. sin(x), sqrt(x))
2. Some functions from N to N, notably:
i) Function t (Lecture 5)
ii) Function p (Lecture 6; Busy Beaver)
iii) h(m,n) - HP function
Basic functions - answers-Zero function (z = 0); successor function (s(0)=1, s(1)=2,...); identity
function (idi(x1,...,xi,...,xn) = xi)
Primitive recursive functions - answers-The smallest class of functions satisfying the following:
1. Every basic function is primitive recursive function
2. (Composition closure) If f and g1,...,gk PR, then Cn[f, g1,...,gk)(x1,...,xn) =
f(g1(x1,...,xn),...,gk(x1,...,xn))
3. (Primitive Recursion closure) If f and g are PR, then Pr[f,g] is also PR, where:
Pr[f,g](x,0) = f(x)
Pr[f, g](x, s(y)) = g(x,y,Pr[f,g](x,y))
Recursive fuctions - answers-The smallest class of functions satisyfying:
1. Every basic function is recursive function
2. Composition closure
3. Primitive Recursion Closure
4. (Minimization Closure) If f is a recursive function, then Mn[f] is a recursive function:
Mn[f](x) = μy[f(x,y) = 0]; undefined otherwise
2
