Comments on: Quantum Computing Since Democritus Lecture 5: Paleocomplexity

By: Scott

Scott — Fri, 27 Oct 2006 17:31:00 +0000

David: If n=-1/2, then e^(2πin) = e^(-πi) = 1/-1 = -1.

e^(2πin) will be -1 if n = 1/2, 3/2, … (or -1/2, -3/2, …), while e^(2πin) will be 1 if n = 0, 1, 2, … (or -1, -2, …).

By: David Moles

David Moles — Fri, 27 Oct 2006 12:52:00 +0000

Well, once we have complex numbers, we can force a number n to be an integer, by saying that we want e^(2πin) to equal 1. I'm sure this is just a humanities major making a dumb arithmetic mistake, but could you point me to a fuller explanation of this? When I tried to solve for n I got -1/2.

By: Greg Kuperberg

Greg Kuperberg — Fri, 27 Oct 2006 03:07:00 +0000

At the risk of a bit of narcissism, I would enjoy a photo of the poster in its environment. (The inclusion graph is the fruit of a serious computer-assisted project.)

By: scott

scott — Thu, 26 Oct 2006 22:31:00 +0000

John: What I meant is that there’s no general algorithm that, given as input a statement about complex numbers with exponentiation, decides whether or not the statement is true. This follows from the fact that such sentences can talk about integers, and if you can talk about integers you can talk about Turing machines, and if you can talk about Turing machines you can formulate both Gödel sentences and the halting problem.

(Unfortunately, the word “undecidable” has several senses — there’s Gödel’s sense of a theory that can formulate its own consistency statement, and there’s Turing’s sense of an algorithmically unsolvable problem. But I hope the above discussion clarifies what I meant.)

By: scott

scott — Thu, 26 Oct 2006 22:20:00 +0000

floor(n*(sin(n)+sqrt(7))) is certainly time-constructible…

Which implies you need to compute a good enough approximation to the function f(n) within time f(n).

No. When I said you have to run for f(n) steps, really I meant O(f(n)) steps. (That’s perfectly sufficient for proving a hierarchy theorem.)

By: John Sidles

John Sidles — Thu, 26 Oct 2006 18:25:00 +0000

Whoop! The Young Frankenstein post had the wrong URL; here’s the correct one. (no, the wrong one wasn’t some kind of lame recursive joke)

By: Chris Dawson

Chris Dawson — Thu, 26 Oct 2006 18:09:00 +0000

Strange, the complexity class inclusion graph looks very familiar. Is it isomorphic to the London underground?

By: john

john — Thu, 26 Oct 2006 16:18:00 +0000

Why is it immediate that once you define integers (e^{pi * i}…) the decision problem becomes undecidable? As I understand it Godel’s theorem says that there are true statements that any sound proof system can’t prove. However isn’t a program that decides this problem free to find a sufficiently powerful (& sound) proof system in which the statement is provable?

By: Anonymous

Anonymous — Thu, 26 Oct 2006 16:16:00 +0000

floor(n*(sin(n)+sqrt(7))) is certainly time-constructible... Which implies you need to compute a good enough approximation to the function f(n) within time f(n). In other words, f(n) is in computable in some sort of exponential time on the size of the output. Why is this so obviously true? It seems to me that the world is full of things that are harder to compute than that.

By: scott

scott — Thu, 26 Oct 2006 14:26:00 +0000

floor(n*(sin(n)+sqrt(7))) is certainly time-constructible…