Logic seminar: David Ross (III)
Mar 10 @ 2:30 pm – 3:30 pm
Kjos-Hanssen: Superposition as memory
Mar 17 @ 2:30 pm – 3:30 pm

The Logic Seminar will meet again this Friday. The speaker will be Bjørn Kjos-Hanssen.

Superposition as memory: unlocking quantum automatic complexity

Friday March 17, 2:30-3:20

Place: Keller 404 (Note: this might change)

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$.

Logic seminar: Achilles Beros @ Keller Hall 404
Mar 24 @ 2:30 pm – 3:30 pm

The Logic Seminar will meet again this Friday, usual place: Keller Hall 404. The speaker will be Achilles Beros.

Title: Teachers, Learners and Oracles

Abstract: When identifying r.e. sets from enumeration, a teacher is a
computational aide that pre-processes the data and only passes the
“useful” examples to the learner. Access to a teacher does not affect
the learnability of a family of r.e. sets, but it can affect the speed
with which learning is accomplished. Another computational aide is the
membership oracle. We consider four different forms of polynomial
bounds on learning and compare the performance of learners equipped with
teachers and learners equipped with oracles. We find that in most cases
neither strategy is uniformly superior. In this talk I will survey the
results and show a proof that utilizes a strategy analogous to integrity
checks in TCP (Transmission Control Protocol). The paper presented is
joint work with Colin de la Higuera.

Logic seminar: Jack Yoon @ Keller 404
Apr 7 @ 2:30 pm – 3:20 pm

The Logic Seminar will meet again this Friday, usual place and time. The speaker will be Jack Yoon.

Title: Proof Mining

Abstract: Proof mining (proof unwinding) is a technique used to extract
constructive information from seemingly non-constructive proofs. We
discuss the idea behind the topic and describe the foundations which
form the basis for proof mining.

Logic Seminar: Jack Yoon @ Keller 404
Apr 28 @ 2:30 pm – 3:30 pm

Jack Yoon will continue his explication of Proof Mining.

Logic Seminar: David Webb
May 5 @ 1:00 pm – May 5 @ 2:00 pm

David Webb will speak at 1:00-2:00 in Keller 402

Title: Every Function Can be Computable

Abstract: I will relay an interesting result of Joel David Hamkins: that
there is an algorithm which can compute any function f of natural
numbers, if it is carried out in the right model of arithmetic
(corresponding to f). In particular, I will construct the necessary
models using Rosser sentences and describe the algorithm.

Logic seminar: David Ross
Aug 31 @ 2:50 pm – 3:40 pm

This semester the Logic Seminar will meet on Thursdays, 2:50 – 3:40 pm in Keller 402.

This Thursday we will have a (probably brief) organizational meeting.

Title: Some nonstandard remarks about Egyptian fractions

Abstract: An Egyptian fraction is a finite sum of fractions of the form $1/n$, where $n$ is a natural number. I’ll give simple proofs of some results about such fractions (also about Znám fractions). The proofs only require the compactness theorem from first order logic, though I’ll use the language of nonstandard analysis.

Logic Seminar: David Webb @ Keller 402
Sep 14 @ 2:50 pm – 3:40 pm

Title: A Simple Proof of a Theorem of Woodin

Abstract: In a similar spirit as my talk last semester about computing
and non-standard models, I will relay Joel David Hamkins’ new proof of a
theorem of Woodin: that there is a function that enumerates any finite
set (if computed in the correct model M of arithmetic), and which can
enumerate any extension of that set (if run in the correct end-extension
of M).