|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness
If you have a question about this talk, please contact Mustapha Amrani.
Semantics and Syntax: A Legacy of Alan Turing
We present some new characterizations of Schnorr triviality. Schnorr triviality is defined using complexity via a computable measure machine, with which Schnorr randomness has a characterization. Since we have a characterization of Schnorr randomness via decidable prefix-free machine, we also have a characterization of Schnorr triviality using complexity via a decidable prefix-free machine. It should be noted that numerous characterizations of Schnorr triviality have the following form: for any computable object, there exists another computable object such that the real is in some object. By defining a basis for Schnorr randomness in a similar manner, we can show the equivalence to Schnorr triviality while Franklin and Stephan (2010) showed that there exists a Schnorr trivial set that is not truth-table reducible to any Schnorr random set.
This talk is part of the Isaac Newton Institute Seminar Series series.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsPalaeolithic-Mesolithic Discussion Group, Department of Archaeology Synthetic Differential Geometry Seminar The Eddington Lectures
Other talksBetween Privilege and Property: Four Conceptions of Copyright in Late-Qing China The first bohemians: the artists of eighteenth-century Covent Garden EDWARD ULLENDORFF AND THE STUDY OF SEMITIC LANGUAGES Spatiotemporal control of motor circuit assembly and function. Raymond and Beverley Sackler Distinguished Lecture No Talk: Summer conference "Mind the Gap"