Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1059

4 Comments & 4 Trackbacks

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(x,y)=ythbitofxthstring g(x,y) = {y}th bit of {x}th string
(2)f(x)=NOTx f(x) = NOT x

Define AA s.t. f(g(x,x))=g(A,x)f(g(x,x)) = g(A,x)

Then g(A,A)=f(g(A,A))=g(A,A) = f(g(A,A)) = NOT g(A,A)g(A,A)

In a similar way, the halting problem has

(3)g(x,y)=x(y)halts g(x,y) = x(y) \; halts
(4)f(x)=NOTx f(x) = NOT x

Define AA s.t. f(g(x,x))=g(A,x)f(g(x,x)) = g(A,x)

i.e.

(5)A(x)={haltsifx(x)doesnothalt loopsotherwiseA(x)=\begin{cases}halts if x(x) does not halt \\ loops otherwise\end{cases}

Then g(A,A)=f(g(A,A))=g(A,A) = f(g(A,A)) = NOT g(A,A)g(A,A)

i.e. g(A,A)g(A,A) 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)

Thanks, I’ll add that link to the references above!

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
Read the post Paris Attactions
Weblog: Paris Attactions
Excerpt: Wow, cool!
Tracked: March 31, 2008 4:59 AM

Post a New Comment