Downloads: 208
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| s00224-013-9506-8.pdf | 218.32 kB | Adobe PDF | View/Open |
| Title: | Schnorr Triviality and Its Equivalent Notions |
| Authors: | Miyabe, Kenshi |
| Author's alias: | 宮部, 賢志 |
| Keywords: | Algorithmic randomness Schnorr randomness Schnorr triviality Uniform relativization |
| Issue Date: | 29-Sep-2013 |
| Publisher: | Springer US |
| Journal title: | Theory of Computing Systems |
| Volume: | 56 |
| Issue: | 3 |
| Start page: | 465 |
| End page: | 486 |
| Abstract: | We give some characterizations of Schnorr triviality. In concrete terms, we introduce a reducibility related to decidable prefix-free machines and show the equivalence with Schnorr reducibility. We also give a uniform-Schnorr-randomness version of the equivalence of LR-reducibility and LK-reducibility. Finally we prove a base-type characterization of Schnorr triviality. |
| Rights: | The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-013-9506-8 この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
| URI: | http://hdl.handle.net/2433/198571 |
| DOI(Published Version): | 10.1007/s00224-013-9506-8 |
| Appears in Collections: | Journal Articles |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.