COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness

## Schnorr triviality is equivalent to being a basis for tt-Schnorr randomnessAdd to your list(s) Download to your calendar using vCal - Miyabe, K (Kyoto University)
- Monday 02 July 2012, 15:00-15:30
- Seminar Room 1, Newton Institute.
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:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsClinical ID talks Centre for Scientific Computing Institute of Continuing Education## Other talksThe Gopakumar-Vafa conjecture for symplectic manifolds Adrian Seminar: Ensemble coding in amygdala circuits Genes against beans: favism, malaria and nationalism in the Middle East Attentional episodes and cognitive control Doctor Who: Gridlock BP KEYNOTE LECTURE: Importance of C-O Bond Activation for CO2/COUtilization - An Approach to Energy Conversion and Storage Cyclic Peptides: Building Blocks for Supramolecular Designs “Modulating Tregs in Cancer and Autoimmunity” LARMOR LECTURE - Exoplanets, on the hunt of Universal life Autumn Cactus & Succulent Show Replication or exploration? Sequential design for stochastic simulation experiments |