BEGIN:VCALENDAR
PRODID:-//PSU Mathematics Department//Seminar iCalendar Generator//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Logic Seminar
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150106T143000
DTEND;TZID=America/New_York:20150106T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24898
SUMMARY:Logic Seminar - TBA
DESCRIPTION:Seminar: Logic Seminar\nTitle: TBA\nAbstract Link: http://
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150113T143000
DTEND;TZID=America/New_York:20150113T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24899
SUMMARY:Logic Seminar - Organizational Meeting
DESCRIPTION:Seminar: Logic Seminar\nTitle: Organizational Meeting\nAbstract
: We will meet to discuss the schedule for the semester.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150120T143000
DTEND;TZID=America/New_York:20150120T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24900
SUMMARY:Logic Seminar - Separation and reduction in second-order arithmetic
DESCRIPTION:Seminar: Logic Seminar\nTitle: Separation and reduction in seco
nd-order arithmetic\nSpeaker: David Belanger\, Cornell University\nAbstrac
t: A family F of subsets of a set Z has the separation property if for eve
ry disjoint pair A\,B in F\, there is a partition of Z into two sets A_0\,
B_0 such that A is a subset of A_0\, B is a subset of B_0\, and A_0\,B_0 a
re both in F. We look at the separation properties for several F\, Z pair
s\, their roles in reverse mathematics\, and a few directions these roles
suggest for future research.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150127T143000
DTEND;TZID=America/New_York:20150127T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24901
SUMMARY:Logic Seminar - Hilbert's Tenth Problem for subrings of the rationa
ls and number fields.
DESCRIPTION:Seminar: Logic Seminar\nTitle: Hilbert's Tenth Problem for subr
ings of the rationals and number fields.\nSpeaker: Kirsten Eisenträger\,
Penn State\nAbstract: In 1970 Matiyasevich\, building on work by Davis\, P
utnam and Robinson\, proved that Hilbert's Tenth Problem is undecidable. S
ince then\, analogues of this problem have been studied by considering pol
ynomial equations over commutative rings other than the integers. The bigg
est open problem in the area is Hilbert's Tenth Problem over the rational
numbers and over number fields in general. In this talk we will construct
some subrings $R$ of the rationals that have the property that Hilbert's T
enth Problem for $R$ is Turing equivalent to Hilbert's Tenth Problem over
the rationals. We will show that the same can be done for number fields. T
he rings will be constructed with a priority argument.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150203T143000
DTEND;TZID=America/New_York:20150203T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24902
SUMMARY:Logic Seminar - The power of uniformity in algorithmic randomness
DESCRIPTION:Seminar: Logic Seminar\nTitle: The power of uniformity in algor
ithmic randomness\nSpeaker: Jason Rute\, Penn State\nAbstract: It is well
known that computable analysis and algorithmic randomness are closely conn
ected. Moreover\, computable analysis suggests that uniform reducibility s
hould play a large role in algorithmic randomness. In this talk I will sho
w an application of this insight. I will prove a product theorem for Schno
rr randomness for non-computable measures. This product theorem is an exte
nsion of van Lambalgen's well-known theorem. Both the proof and the statem
ent of the theorem rely heavily on uniformity. It also uses computable ana
lysis in important and insightful ways.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150210T143000
DTEND;TZID=America/New_York:20150210T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24903
SUMMARY:Logic Seminar - Initial segment complexity and randomness for compu
table measures
DESCRIPTION:Seminar: Logic Seminar\nTitle: Initial segment complexity and r
andomness for computable measures\nSpeaker: Christopher P. Porter\, Univer
sity of Florida\nAbstract: According to the Levin-Schnorr theorem\, a sequ
ence $X$ is Martin-Lö\;f random with respect to the Lebesgue measure i
f and only if $K(X\\upharpoonright n)\\geq n-O(1)$ for every $n$\, where $
K$ denotes prefix-free Kolmogorov complexity. It is well-known that this
theorem can be extended to proper sequences\, that is\, sequences that are
random with respect to some computable measure. Nonetheless\, one can sh
ow that there are proper sequences with slow-growing initial segment compl
exity (i.e.\, there is no computable lower bound for their initial segment
complexity). I will discuss joint work with Rupert Hö\;lzl and Wolfg
ang Merkle in which we study the various growth rates of the initial segme
nt complexity of proper sequences.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150217T143000
DTEND;TZID=America/New_York:20150217T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24904
SUMMARY:Logic Seminar - Effective Theory of Levy Processes
DESCRIPTION:Seminar: Logic Seminar\nTitle: Effective Theory of Levy Process
es\nSpeaker: Adrian Maler\, Penn State\nAbstract: We define a "computable"
Levy process in three ways\, discuss their equivalence\, and present an e
ffective version of the Levy-Ito decomposition.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150224T143000
DTEND;TZID=America/New_York:20150224T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24905
SUMMARY:Logic Seminar - Degrees of unsolvability: some recent results
DESCRIPTION:Seminar: Logic Seminar\nTitle: Degrees of unsolvability: some r
ecent results\nSpeaker: Stephen G. Simpson\, Pennsylvania State University
\nAbstract: A mass problem is a set of reals. If P and Q are mass problem
s\, we say that P is Muchnik reducible to Q if for each real y in Q there
exists a real x in P such that x is Turing reducible to y. A Muchnik degr
ee is an equivalence class of mass problems under mutual Muchnik reducibil
ity. It is well known that the lattice of all Muchnik degrees provides a
rigorous implementation of Kolmogorov's nonrigorous 1932 interpretation of
intuitionism as a "calculus of problems" (Aufgabenrechnung). In this tal
k I will discuss some recent results concerning the sublattice consisting
of the Muchnik degrees of nonempty\, effectively closed sets of reals.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150303T143000
DTEND;TZID=America/New_York:20150303T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24906
SUMMARY:Logic Seminar - Kolmogorov Random Graphs
DESCRIPTION:Seminar: Logic Seminar\nTitle: Kolmogorov Random Graphs\nSpeake
r: John Pardo\, Penn State\nAbstract: We will discuss several properties o
f Kolmogorov random graphs using deficiency functions\, i.e. functions tha
t bound how far away a graph is from maximum complexity\, and relate these
properties back to the usual notion of randomness for binary strings as w
ell as connect them to the property of quasirandomness.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150310T143000
DTEND;TZID=America/New_York:20150310T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24907
SUMMARY:Logic Seminar - NO SEMINAR\, SPRING BREAK
DESCRIPTION:Seminar: Logic Seminar\nTitle: NO SEMINAR\, SPRING BREAK
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150317T143000
DTEND;TZID=America/New_York:20150317T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24908
SUMMARY:Logic Seminar - Strong treeability of planar groups
DESCRIPTION:Seminar: Logic Seminar\nTitle: Strong treeability of planar gro
ups\nSpeaker: Clinton Conley\, Carnegie Mellon University\nAbstract: An eq
uivalence relation is called treeable if it can be realized as the connect
edness relation of an acyclic Borel graph. We call a finitely generated g
roup planar if there is some finite generating set such that the induced C
ayley graph of the group is planar. Using techniques originally created t
o analyze measure-theoretic chromatic numbers of graphs\, we show that any
orbit equivalence relation of a free measure-preserving action of a plana
r group on a standard probability space is treeable on a conull set. This
is joint work with Gaboriau\, Marks\, and Tucker-Drob.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150324T143000
DTEND;TZID=America/New_York:20150324T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24909
SUMMARY:Logic Seminar - Precisely Constructed Taxa and Higher Order Dangers
in Models of Randomness
DESCRIPTION:Seminar: Logic Seminar\nTitle: Precisely Constructed Taxa and H
igher Order Dangers in Models of Randomness\nSpeaker: Steven Pincus\, Guil
ford\, CT\nAbstract: The certification\, explicit construction and delinea
tion of individual\, infinite length `random` sequences have been longstan
ding\, yet incompletely resolved problems. We address this topic via the s
tudy of normal numbers\, which have often been viewed as reasonable proxie
s for randomness\, given their limiting equidistribution of subblocks of a
ll lengths. However\, limitations arise within this perspective. First\, w
e develop several criteria motivated by classical theorems for symmetric r
andom walks\, which lead to algorithms for generating normal numbers that
satisfy a variety of attributes for the series of initial partial sums\, i
ncluding rates of sign changes\, patterns of return times to 0\, and the e
xtent of fairness of the sequence. Such characteristics are generally unad
dressed in most evaluations of `randomness`. Second\, we explicitly constr
uct a normal number that satisfies the Law of the Iterated Logarithm (LIL)
\, yet exhibits pairwise bias towards repeated values\, rendering it inapp
ropriate for any collection of random numbers. Accordingly\, we deduce tha
t the evaluation of higher order block dynamics\, even beyond limiting equ
idistribution and fluctuational typicality\, is imperative in proper evalu
ation of sequential `randomness`. More broadly\, we can now differentiate
normal numbers both on the basis of multiple distinct qualitative attribut
es\, as well as quantitatively via a spectrum of rates within each attribu
te. Furthermore\, we exhibit a toolkit of techniques to construct normal s
equences that realize diverse a priori specifications\, including profound
biases. Overall\, we elucidate the vast diversity within the category of
normal sequences.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150331T143000
DTEND;TZID=America/New_York:20150331T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24910
SUMMARY:Logic Seminar - No Seminar this week
DESCRIPTION:Seminar: Logic Seminar\nTitle: No Seminar this week\nSpeaker: N
o Seminar this week
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150417T153500
DTEND;TZID=America/New_York:20150417T163500
LOCATION:MB106
URL:http://www.math.psu.edu/seminars/meeting.php?id=24889
SUMMARY:Logic Seminar - Randomness and Birkhoff's ergodic theorem for measu
re-preserving transformations
DESCRIPTION:Seminar: Logic Seminar\nTitle: Randomness and Birkhoff's ergodi
c theorem for measure-preserving transformations\nSpeaker: Johanna Frankli
n\, Hofstra University\nAbstract: A point in a probability space is algori
thmically random if it has no rare measure-theoretic properties that are d
efined simply\, and ergodic theorems describe regular measure-theoretic be
havior. I will discuss Birkhoff’s ergodic theorem with respect to transf
ormations that are measure-preserving but not necessarily ergodic in the c
ontext of a computable probability space. Then I will show that each point
in such a space that is not Martin-Loef random fails to satisfy Birkhoff
s ergodic theorem with respect to every computable set and measure-prese
rving transformation.\n\nThis work is joint with Henry Towsner.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150421T143000
DTEND;TZID=America/New_York:20150421T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24913
SUMMARY:Logic Seminar - Aspects of the Muchnik lattice
DESCRIPTION:Seminar: Logic Seminar\nTitle: Aspects of the Muchnik lattice\n
Speaker: Stephen G. Simpson\, Pennsylvania State University\nAbstract: Let
P and Q be sets of reals. Intuitively we may view a set of reals as a “
problem\,” namely\, the problem of “finding” some real in the set. A
ccordingly\, we say that P is Muchnik reducible to Q if for all y in Q the
re exists x in P such that x is Turing reducible to y. The Muchnik degree
of P is the equivalence class of P under mutual Muchnik reducibility. Let
D_w be the lattice of all Muchnik degrees\, and let E_w be the sublattice
consisting of the Muchnik degrees of nonempty\, effectively closed (i.e.\,
Pi^0_1) sets of reals. It is well known that D_w is the natural completio
n of the upper semilattice D_T of Turing degrees. Similarly\, E_w is a nat
ural extension of the upper semilattice E_T of recursively enumerable Turi
ng degrees. In a recent paper by Sankha S. Basu and the speaker\, we show
that the category of sheaves of sets over E_w is an interesting model of i
ntuitionistic higher-order logic. We call this model the Muchnik topos. In
recent work by Stephen E. Binns and Richard A. Shore and the speaker\, we
show that E_w is dense\, i.e.\, for all p\, q in E_w such that p < q ther
e exists r in E_w such that p < r < q. We sketch the proof of this latter
result. The proof involves some hyperarithmetical theory.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150428T143000
DTEND;TZID=America/New_York:20150428T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24914
SUMMARY:Logic Seminar - TBA
DESCRIPTION:Seminar: Logic Seminar\nTitle: TBA\nAbstract Link: http://
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150505T143000
DTEND;TZID=America/New_York:20150505T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24915
SUMMARY:Logic Seminar - TBA
DESCRIPTION:Seminar: Logic Seminar\nTitle: TBA\nAbstract Link: http://
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20150512T143000
DTEND;TZID=America/New_York:20150512T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=24916
SUMMARY:Logic Seminar - TBA
DESCRIPTION:Seminar: Logic Seminar\nTitle: TBA\nAbstract Link: http://
END:VEVENT
END:VCALENDAR