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$.
Speaker: Ben Hutz (Saint Louis U.)
Title: A bound on the periodic part of the forward orbit of a projective subvariety
Abstract: Let $f:mathbb{P}^N to mathbb{P}^N$ be a morphism and $X subseteq mathbb{P}^N$ a (projective) variety. We obtain a bound on the periodic part of the forward orbit of $X$ by examining the orbit modulo a prime of good reduction. This bound depends only on the degree of the map, the degree of the subvariety, the dimension of the projective space, the degree of the number field, and the prime of good reduction.
This talk will be split into two different cases. First, a review of the case when $dim(X) = 0$, i.e., iteration of points. For the projective line, a series of results due to Li, Morton-Silverman, Narkiewicz, Pezda, and Zieve provide the main theorem. This was generalized by the speaker in 2009 to any $N$. Second, the main part of the talk describes the speaker’s new result for the case $dim(X) > 0$.
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.
Title: Introduction to Typed Lambda Calculus
Speaker: William DeMeo
Abstract: This is an introduction to the typed lambda calculus, a language for describing functions and tuples, with sum, product and function types. We briefly review the history and motivation of lambda calculus as an alternative to Turing machines. We discuss the syntax of lambda calculus and give some examples. Finally, we consider some reasons for choosing constructive type theory as a framework for doing math.
This is the first in a series of 6 meetings 3/28–4/1 (3 lectures at 11am and 3 hands-on practice sessions at 1:30pm).
(hands on exercise session; follow-up to 11am lecture on typed lambda calculus)
Title: Introduction to Type Theory
Speaker: William DeMeo
Abstract: Type Theory is a foundation for mathematics and computer science and was developed by logicians like Alonzo Church and Per Martin-Löf. Suitable as a basis for computer-assisted proof, it is receiving increasing interest from mathematicians (e.g., for verifying mathematical proofs) and computer scientists (e.g. for verifying compilers and operating systems). Type theory is based on the Curry-Howard Isomorphism, which describes a precise relationship between proofs of a proposition and programs of the corresponding type. In this brief course, we introduce the basics of Type Theory, and practice programming and proving in one of several software implementations of the theory.
(hands on practice session to accompany 11am lecture)
Title: Introduction to Typed Lambda Calculus
Speaker: William DeMeo
Abstract: This is an introduction to the typed lambda calculus, a language for describing functions and tuples, with sum, product and function types. We briefly review the history and motivation of lambda calculus as an alternative to Turing machines. We discuss the syntax of lambda calculus and give some examples. Finally, we consider some reasons for choosing constructive type theory as a framework for doing math.
This is the first in a series of 6 meetings 3/28–4/1 (3 lectures at 11am and 3 hands-on practice sessions at 1:30pm).