Lecture on undecidability

Info:

  • Lecture: during SS11 every Tuesday 12:15-13:45 in room 03.10.011, Zentrum Mathematik TUM, Boltzmannstr.3
  • Exercises: every Thursday 12:15-13:00 (starting May 12), same place.
  • Exam will be oral (about 25min each) on Tuesday 02-08 and Thursday 11-08.
  • A first pdf version of the lecture course posts has been produced by Stefan Kranich and can be found here: pdf-script

Content:

The course is an introductory course on the limitations to what is computable or provable. Topics addressed include: recursion theory, basic results by Church, Turing and Gödel, basics of mathematical logic, undecidable problems like the Halting problem, Hilbert’s 10th problem, Post’s correspondence problem, problems related to semigroups, etc. Consequences in computer science, physics and engineering will be outlined.

Prerequisites:

Basic analysis and algebra. Some familiarity with any programming language and the basic notions of mathematical logic is helpful.

Lectures:

Literature: (on which parts of the lecture are based on)


Exercises discussed on July 21, 2011:

1. For any polynomial  p(x_1,\ldots,x_n) with integer coefficients let N(p) be the cardinal number of the subset \{x\in\mathbb{N}^n|p(x)=0\}. Call a set of cardinal numbers \leq \aleph_0 ‘non-trivial’ if it is neither empty nor does it contain all such cardinal numbers. Prove that for any given non-trivial set C of cardinal numbers \leq \aleph_0 there cannot be any algorithm which decides whether or not N(p)\in C for any polynomial with integer coefficients. (Hint: note that C=\{0\} is Hilbert’s tenth problem. Consider the following three further cases and reduces them to this known one: (i) 0,\aleph_0\in C, (ii) 0\in C, \aleph_0\not\in C, (iii) 0\not\in C.)

2. In the lecture we proved that the class of diophantine sets (in \mathbb{N}^k, say) is closed under unions and intersections. Can you show that it is closed under taking complements?

3. Specify a subset of \mathbb{N} which is not diophantine.

4. Present an idea for the busy beaver award …


Exercises discussed on July 14:

1. We will now approach Hilbert’s 10th problem. Let P be the set of all multivariate polynomials with integer coefficients (i.e., including objects like x_1^3 -13 x_1x_2 -x_3^5).

a) assume there is an ‘oracle’ capable of deciding whether or not any element p\in P has an integral root, i.e., a solution of p(x)=0 for which x\in\mathbb{Z}^n where n is the number of variables of p. Show that by using the oracle we can decide whether or not there is a non-negative integral root, i.e.,  0\in p(\mathbb{N}^n).

b) show the same as in a) but the other way round: assuming the oracle can deal with non-negative integral roots, provide a method for deciding the existence of an integral root.

c) assume that the oracle accepts only polynomials of degree four or less (i.e. terms like x_1x_2x_3^2 and x_1^4 are accepted but x_1^5 isn’t). Show that we can still exploit the oracle in order to decide the existence of an integral root for any polynomial (including those of higher degree). Hint: recursively replace monomials of degree two by new variables (i.e., y_1=x_1x_2, z_1=y_1x_3 etc.) and incorporate the constraints by summing up their squares.

d) assume we’re interested in the existence of a root within \mathbb{Z}_d^n. Is this problem recursively decidable?

e) assume we we’re interested in the existence of an integral root for the subset of P which contains only polynomials for which the degree, the number of variables and the absolut value of the coefficients are all bounded by 42. Is this problem recursively decidable?

f) is there a (practically relevant) difference between d) and e) ?

2. Present an idea for the busy beaver award 🙂

Exercises discussed on July 7:

1.  For words w=a_1\ldots a_m over the alphabet \{0,1\} define a map \psi(w):=\psi'(a_1)\cdots\psi'(a_m) as a product of matrices of the form  \psi'(a_i):=\left(\begin{array}{cc} 1&a_i\\ 0&2\end{array}\right). Similarly, define \phi(w):=[\psi'(a_m)]^{-1}\cdots[\psi'(a_1)]^{-1}.

a) prove that \psi is an isomorphism between the monoid \{0,1\}^* and the one generated by the matrices \psi'(0),\psi'(1) and the identity matrix {\bf 1} if we set \psi(e):=\bf 1.

b) Consider any PCP(n) instance given by n pairs (X_1,Y_1), \ldots, (X_n,Y_n) of words in \{0,1\}^*. Construct a product of matrices (using \phi and \psi) which is equal to the identity matrix iff there is a solution to the PCP problem (meaning that there exists a sequence m of some finite length N so that X_{m_1}\cdots X_{m_N}=Y_{m_1}\cdots Y_{m_N}).

c) Note that all the involved matrices are of the form \left(\begin{array}{cc} 1&x\\ 0&y\end{array}\right) for some (x,y)\in \mathbb{Q}^2. Assign one affine transformation T_i:\mathbb{Q}^2\rightarrow\mathbb{Q}^2 to every PCP pair (X_i,Y_i) such that there is a PCP solution iff there exists a sequence  T_{m_N}\cdots T_{m_1} of those affine transformations which maps the vector (0,1) onto itself.

d) Prove an analogous result where affine transformations on \mathbb{Q}^2 are replaced by linear transformations on \mathbb{Q}^3.

2. Consider the subset of PCP(n) problems over a binary alphabet where there is the additional constraint that the length of all words X_j,Y_j is bounded by some constant c\in\mathbb{N}. For which n is this problem decidable/undecidable?

3. Busy beaver award: One of the participants of the course is awarded a decent book prize if he/she:

  1. finds a new provably undecidable problem (i.e., one which is not an epsilon modification of a published result), or
  2. shows that a problem is decidable which was not known to be decidable before and is not obviously so [one possibility would be to show decidability of matrix mortality for 3 2×2 matrices], or
  3. finds an application or interpretation of a known undecidable problem in terms of a problem which is (i) considered by more than 42 people and (ii) such that its undecidability was not known before.

If there are more candidates the participants decide which one is awarded. This ‘offer’ lasts until August 31, 2011.

 Exercises discussed on June 30:

1. Is the following set S_7\subset\mathbb{N} recursively enumerable?  S_7:=\{x|F_x(7)\ undefined\}

2. Regard the function f_1 defined in a previous lecture as the characteristic function of a set. Is this set recursively enumerable?

3. In the lecture two types of ‘halting problems’ for a universal TM appeared. They ask whether or not (and depending on the input) (i) the TM halts or (ii) the TM halts in standard configuration. Argue, possibly employing the Church-Turing thesis, that undecidability of (ii) implies undecidability of (i).

4. For words w=a_1\ldots a_m over the alphabet A:=\{1,2,3\} define a map W(w):=\sum_{k=1}^m a_k 4^{m-k} from A^* to \mathbb{N}. Denote by |w| the length of a word and define a map from A^*\times A^* into the set of 3×3 integer matrices by

M_{u,w}:=\left(\begin{array}{ccc} 4^{|u|}&0&0\\ 0&4^{|w|}&0\\ W(u)&W(w)&1\end{array}\right).

Prove that (u,w)\mapsto M_{u,w} is a monoid monomorphism if we use concatenation of words and matrix multiplication as binary operations in the domain and codomain respectively.

Exercises discussed on June 16: 

1. Let S\subset\mathbb{N} be non-empty set which is the range of a recursive partial function on \mathbb{N}^k. Prove that there is a primitive recursive function g:\mathbb{N}\rightarrow\mathbb{N} such that its range equals S. [hint: use the normal-form theorem and pairing functions introduced here]

2. Show that if two sets are recursive, then their intersection and union are recursive sets as well.

3. Let A and B be subsets of \mathbb{N}. Construct a set C\subseteq\mathbb{N} which is recursive iff both A and B are.

Exercises discussed on June 9: 

1. Can you write a program (using your favorite programming language) which prints its own source code?

2. Prove that for any recursive function f:\mathbb{N}^2\rightarrow\mathbb{N} there exists an m\in\mathbb{N} so that F_m(y)=f(m,y) for all y. (Use the s-m-n theorem and the recursion theorem)

3. Using the result of the previous problem, show that there is an n\in\mathbb{N} so that F_n(x)=n for all x. (Do under no circumstances think about a relation with problem 1.)

4. Use the recursion theorem to show that the Ackermann function is recursive. Hint: define a three-argument function by cases which mimic the defining relations of the Ackermann function (e.g., set g(n,x+1,y+1):=F(n,x,F(n,x+1,y)), g(n,x+1,0):=F(n,x,1), g(n,0,y):=y+1 ).

Exercises discussed on May 26: 

1. Provide a formal representation (i.e., Cn[Pr[Cn[\ldots) of the factorial function 😉

2. Prove that for any rational number x\in [0,1) with decimal expansion x=0. x_0 x_1 x_2 \ldots there is a primitive recursive function such that f(n)=x_n for all n\in\mathbb{N} (hint: think about a characteristic property of rational numbers regarding  their decimal expansion).

3. A primitive recursive function similar to that in exercise 2. exists not only for rational numbers; explicit representations are known for various roots, \pi/4, e/3, etc. Can there be a real number x \in[0,1) for which no such primitive recursive function exists? Why?

Exercises discussed on May 19: 

1. Show that the cardinality of the set of algebraic numbers does not contradict the continuum hypothesis.

2. Show whether or not the function f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N} defined by f(x,y)=|x-y| is primitive recursive.

3. Prove that the predicates x\geq y and x\neq y are primitive recursive.

4. Identify the function Cn[Pr[Cn[s,z],Cn[prod,id_3^3,id_2^3]],id_1^1,id_1^1]

Exercises discussed on May 12: 

1. Look up what Richard’s paradox is.

2. Recall the meaning of the quantifiers for all \forall and there exists \exists as well as of the Boolean operations and \wedge and or \vee. Let a,b,c,x,y\in \mathbb{N}. What’s the meaning of the following statements:

a) \forall a\exists b\forall x,y \big(b>a\wedge(x,y>1\rightarrow xy\neq b)\big)

b) \forall a \exists b\forall x,y \big(b>a\wedge(x,y>1\rightarrow (xy\neq b\wedge xy\neq b+2))\big)

c) \forall a\exists b,c,x,y (a=b^2+c^2+x^2+y^2)

Formulate Fermat’s last theorem and Goldbach’s conjecture (which you both may look up somewhere) in a similar way.

3. Define a function f:\mathbb{N}\rightarrow\{0,1\} by f(x):=0 if statement b) above is false and f(x):=1 if it is true. Can you write an algorithm which computes the function? Can you prove or disprove that f(1)=1?

4. What’s the biggest natural number for which you can give a precise mathematical definition and explain it in, say 20 seconds, to your fellow student? Remember that ‘infinity’ is not a natural number and something like in Berry’s paradox doesn’t work …

5. Compute BB(1), i.e., the value of the busy beaver function for n=1.

Leave a comment