Classical vs Quantum Computation (Week 8)
Posted by John Baez
Here are the last of the Fall quarter notes on Classical versus Quantum Computation:
- Week 8 (Nov. 30) - The Fixed Point Theorem and the diagonal argument (after Tom Payne). Cantor’s ‘negative’ use of diagonalization to prove that infinite bit strings cannot be enumerated, versus Curry’s ‘positive’ use of diagonalization to get a fixed point for any lambda-term in the untyped lambda calculus. Preview of coming attractions: quantum computation, and categorifying everything so far to see computation as a process.
Last week’s notes are here; next week’s notes are here.
Last time we proved that every lambda-term in the untyped lambda calculus has a fixed point, but the proof looked like magic: we pulled a rabbit out of a hat. This time, following Tom Payne’s comments, we explained where such rabbits come from. In fact, Curry’s construction of a fixed point for any lambda-term is based on the same ideas as Cantor’s diagonal argument!
For more along these lines, try these:
- F. William Lawvere, Diagonal arguments and cartesian closed categories, with author commentary, Reprints in Theory and Applications of Categories 15. Originally published in Category Theory, Homology Theory, and their Applications II, eds. Dold and Eckmann, Springer Lecture Notes in Mathematics 92, 1969, pp. 134–145.
- Noson Yanofsky, A universal approach to self-referential paradoxes, incompleteness and fixed points.
Lawvere’s paper begins:
The similarity between the famous arguments of Cantor, Russell, Gödel and Tarski is well-known, and suggests that these arguments should all be special cases of a single theorem about a suitable kind of abstract structure. We offer here a fixed-point theorem in cartesian closed categories which seems to play this role.
Yanofsky’s paper is expository and lots of fun. Now he’s writing a book on quantum computation for computer scientists. One of my grad students, Alex Hoffnung, previously studied with him.
We also gave a preview of coming attractions: more on quantum computation, and categorifying our work so far to see the process of computation as a 2-morphism in a 2-category.
This is my last class this quarter, since next Thursday I’ll be giving a talk at Stanford. In my absence, Tom Payne will speak about the Myhill-Shepherdson Theorem. We’ll continue in January!
Fitting the halting problem to the template in the notes
You showed using a diagonal argument that you can’t list all binary sequences:
Define $A$ s.t. $f(g(x,x)) = g(A,x)$
Then $g(A,A) = f(g(A,A)) =$ NOT $g(A,A)$
In a similar way, the halting problem has
Define $A$ s.t. $f(g(x,x)) = g(A,x)$
i.e.
Then $g(A,A) = f(g(A,A)) =$ NOT $g(A,A)$
i.e. $g(A,A)$ halts iff it doesn’t.