Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness
Duration: 23 mins 39 secs
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Miyabe, K (Kyoto University)
Monday 02 July 2012, 15:00-15:30 |
|---|
| Created: | 2012-07-10 15:50 |
|---|---|
| Collection: | Semantics and Syntax: A Legacy of Alan Turing |
| Publisher: | Isaac Newton Institute |
| Copyright: | Miyabe, K |
| Language: | eng (English) |
| Abstract: | 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. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.85 Mbits/sec | 328.18 MB | View | Download | |
| WebM | 640x360 | 1.02 Mbits/sec | 182.71 MB | View | Download | |
| Flash Video | 484x272 | 568.85 kbits/sec | 98.54 MB | View | Download | |
| iPod Video | 480x270 | 506.01 kbits/sec | 87.71 MB | View | Download | |
| MP3 | 44100 Hz | 125.03 kbits/sec | 21.54 MB | Listen | Download | |
| Auto * | (Allows browser to choose a format it supports) | |||||