## December 1, 2006

### 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:

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!

Posted at December 1, 2006 1:21 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1059

Read the post Classical vs Quantum Computation (Week 7)
Weblog: The n-Category Café
Excerpt: Building a computer using the lambda calculus: the Fixed Point Theorem.
Tracked: December 1, 2006 1:42 AM

### Fitting the halting problem to the template in the notes

You showed using a diagonal argument that you can’t list all binary sequences:

(1)$g\left(x,y\right)=y\mathrm{th}\mathrm{bit}\mathrm{of}x\mathrm{th}\mathrm{string}$
(2)$f\left(x\right)=\mathrm{NOT}x$

Define $A$ s.t. $f\left(g\left(x,x\right)\right)=g\left(A,x\right)$

Then $g\left(A,A\right)=f\left(g\left(A,A\right)\right)=$ NOT $g\left(A,A\right)$

In a similar way, the halting problem has

(3)$g\left(x,y\right)=x\left(y\right)\phantom{\rule{thickmathspace}{0ex}}\mathrm{halts}$
(4)$f\left(x\right)=\mathrm{NOT}x$

Define $A$ s.t. $f\left(g\left(x,x\right)\right)=g\left(A,x\right)$

i.e.

(5)$A\left(x\right)=\left\{\begin{array}{l}\mathrm{halts}\mathrm{if}x\left(x\right)\mathrm{does}\mathrm{not}\mathrm{halt}\\ \mathrm{loops}\mathrm{otherwise}\end{array}$

Then $g\left(A,A\right)=f\left(g\left(A,A\right)\right)=$ NOT $g\left(A,A\right)$

i.e. $g\left(A,A\right)$ halts iff it doesn’t.

Posted by: Mike Stay on December 1, 2006 11:31 PM | Permalink | Reply to this

### Re: Fitting the halting problem to the template in the notes

Excellent!

Thanks for getting the halting problem into this format, Mike.

Posted by: John Baez on December 2, 2006 5:03 AM | Permalink | Reply to this

### Re: Classical vs Quantum Computation (Week 8)

Lawvere’s paper may also be found here. It’s certainly worth a read.

Posted by: Todd Trimble on December 2, 2006 2:59 PM | Permalink | Reply to this

### Re: Classical vs Quantum Computation (Week 8)

Posted by: John Baez on December 2, 2006 6:00 PM | Permalink | Reply to this
Read the post Guiraud on Higher-Dimensional Rewrite Rules
Weblog: The n-Category Café
Excerpt: The three dimensions of proof.
Tracked: December 6, 2006 1:35 AM
Read the post Classical vs Quantum Computation (Week 9)
Weblog: The n-Category Café
Excerpt: Now we'll categorify the concept of 'category' to see computation as a process!
Tracked: January 5, 2007 12:39 AM
Weblog: Paris Attactions
Excerpt: Wow, cool!
Tracked: March 31, 2008 4:59 AM

Post a New Comment