The Sporadic Logic Seminar returns this week at a new place and time
(Fridays, 2:30, K404). This week Mushfeq Khan will speak:
Title: “The Homogeneity Conjecture”
Abstract: It is often said that the theorems and methods of recursion theory
relativize. One might go as far as to say that much of its analytical power
derives from this feature. However, this power is accompanied by definite
drawbacks: There are important examples of theorems and open questions
whose statements are non-relativizing, i.e., they have been shown to be
true relative to some oracles, and false relative to others. It follows
that these questions cannot be settled purely through relativizing methods.
A famous example of such a negative result is Baker, Gill, and Solovay’s
theorem on the P vs. NP question.
The observation that techniques based on diagonalization, effective
numbering, and simulation relativize led some recursion theorists (notably
Hartley Rogers, Jr) to formulate what became known as the “Homogeneity
Conjecture”. It said that for any Turing degree d, the partial order of
degrees that are above d is isomorphic to the entire partial order of the
Turing degrees. In 1979, Richard Shore refuted it in an elegant, one-page
article which will be the subject of this talk.
Title: Some applications of logic to additive number theory
Abstract: I will review the Loeb measure construction; I will
assume some exposure to nonstandard analysis, or at least 1st order logic,
comparable to the review I gave last semester in my seminars on fixed
points. Time permitting I will give the Loeb-measure proof of Szemeredi’s
Theorem.
Logic seminar: David Ross
Title: Some applications of logic to additive number theory (cont.)
Room: Keller 404.
Abstract:
I will continue with some examples of results about sets of positive upper Banach density proved using Loeb measures.
The Logic Seminar will meet again this Friday. The speaker will be Bjørn Kjos-Hanssen.
Title:
Superposition as memory: unlocking quantum automatic complexity
Time:
Friday March 17, 2:30-3:20
Place: Keller 404 (Note: this might change)
Abstract:
Imagine a lock with two states, “locked” and “unlocked”, which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states “locked” and “unlocked”, where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan–Schur lemma that a similar lock is not possible for $n=60$.