- 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
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.
Basic analysis and algebra. Some familiarity with any programming language and the basic notions of mathematical logic is helpful.
- 0: Historical bits and pieces
- 1: What’s an algorithm?
- 2: Turing machines and busy beavers
- 3: Primitive recursion
- 3b: Gödel numbers, codes, indices
- 4: Limitations of primitive recursion
- 5: Recursive functions vs. Turing computability
- 6: Basic theorems of recursion theory
- 6b: Rice’s theorem and the Church-Turing thesis
- 6c: Recursively enumerable sets
- 7: The word problem for Thue systems
- 7b: Word problems for (semi-)group presentations
- 8: Post’s correspondence problem
- 8b: Undecidable matrix problems
- 9: Hilbert’s 10th problem
- 10: Implications for mathematical logic
Literature: (on which parts of the lecture are based on)
- M.Davis: The universal computer (further reading for lecture 0)
- H. Rogers: Theory of recursive functions and effective computability (1)
- Boolos, Burgess and Jeffrey: Computability and Logic (3,5)
- Cutland: Computability (6,10)
- J.J. Kari: Automata and formal languages (8)
- P Bell, I Potapov: Lowering undecidability bounds (8)
- M.Davis in Handbook of Mathematical Logic (7,9)
Exercises discussed on July 21, 2011:
1. For any polynomial with integer coefficients let be the cardinal number of the subset . Call a set of cardinal numbers ‘non-trivial’ if it is neither empty nor does it contain all such cardinal numbers. Prove that for any given non-trivial set of cardinal numbers there cannot be any algorithm which decides whether or not for any polynomial with integer coefficients. (Hint: note that is Hilbert’s tenth problem. Consider the following three further cases and reduces them to this known one: (i) , (ii) , (iii) .)
2. In the lecture we proved that the class of diophantine sets (in , say) is closed under unions and intersections. Can you show that it is closed under taking complements?
3. Specify a subset of 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 be the set of all multivariate polynomials with integer coefficients (i.e., including objects like ).
a) assume there is an ‘oracle’ capable of deciding whether or not any element has an integral root, i.e., a solution of for which where is the number of variables of . Show that by using the oracle we can decide whether or not there is a non-negative integral root, i.e., .
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 and are accepted but 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., etc.) and incorporate the constraints by summing up their squares.
d) assume we’re interested in the existence of a root within . Is this problem recursively decidable?
e) assume we we’re interested in the existence of an integral root for the subset of 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 over the alphabet define a map as a product of matrices of the form . Similarly, define .
a) prove that is an isomorphism between the monoid and the one generated by the matrices and the identity matrix if we set .
b) Consider any PCP(n) instance given by pairs of words in . Construct a product of matrices (using and ) which is equal to the identity matrix iff there is a solution to the PCP problem (meaning that there exists a sequence of some finite length so that ).
c) Note that all the involved matrices are of the form for some . Assign one affine transformation to every PCP pair such that there is a PCP solution iff there exists a sequence of those affine transformations which maps the vector onto itself.
d) Prove an analogous result where affine transformations on are replaced by linear transformations on .
2. Consider the subset of PCP(n) problems over a binary alphabet where there is the additional constraint that the length of all words is bounded by some constant . For which 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:
- finds a new provably undecidable problem (i.e., one which is not an epsilon modification of a published result), or
- 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
- 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 recursively enumerable?
2. Regard the function 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 over the alphabet define a map from to . Denote by the length of a word and define a map from into the set of 3×3 integer matrices by
Prove that 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 be non-empty set which is the range of a recursive partial function on . Prove that there is a primitive recursive function such that its range equals . [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 . Construct a set 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 there exists an so that for all . (Use the s-m-n theorem and the recursion theorem)
3. Using the result of the previous problem, show that there is an so that for all . (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 ).
Exercises discussed on May 26:
1. Provide a formal representation (i.e., ) of the factorial function 😉
2. Prove that for any rational number with decimal expansion there is a primitive recursive function such that for all (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, , , etc. Can there be a real number 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 defined by is primitive recursive.
3. Prove that the predicates and are primitive recursive.
4. Identify the function
Exercises discussed on May 12:
1. Look up what Richard’s paradox is.
2. Recall the meaning of the quantifiers for all and there exists as well as of the Boolean operations and and or . Let . What’s the meaning of the following statements:
Formulate Fermat’s last theorem and Goldbach’s conjecture (which you both may look up somewhere) in a similar way.
3. Define a function by if statement b) above is false and if it is true. Can you write an algorithm which computes the function? Can you prove or disprove that ?
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.