✦ LIBER ✦

Truth-table Schnorr randomness and truth-table reducible randomness

✍ Scribed by Kenshi Miyabe

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 172 KB
Volume: 57
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.200910128

No coin nor oath required. For personal study only.

✦ Synopsis

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen's Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness (defined in [6] too only by martingales) and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness.

📜 SIMILAR VOLUMES

On Pseudo-Creative Sets, Splinters, and

On Pseudo-Creative Sets, Splinters, and Bounded-Truth-Table Reducibility

✍ Paul R. Young 📂 Article 📅 1967 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB

Deterministic and Randomized Bounded Tru

Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets

✍ Dieter van Melkebeek 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 545 KB

We prove that there is no sparse hard set for P under logspace computable bounded truth-table reductions unless P=L. In case of reductions computable in NC 1 , the collapse goes down to P=NC 1 . We parameterize this result and obtain a generic theorem allowing us to vary the sparseness condition, th

An empirical comparison of random number

An empirical comparison of random numbers acquired by computer-generation and from the Rand tables

✍ J.Richard Landis; Alvan R. Feinstein 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 341 KB

The use of Monte Carlo and other statistical procedures that depend on randomization of the observed data has been inhibited by uncertainty about the validity of random numbers generated by a computer. In the empirical test performed here, computergenerated numbers appeared to be just as "random" as

Tables of Random Permutations. By Lincol

Tables of Random Permutations. By Lincoln E. Moses and Robert V. Oakford. Stanford University Press, Stanford, Calif., 1963. 233 pp. 15.5 × 23.5 cm. Price $7

📂 Article 📅 1963 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

Subjective equivalence of sinusoidal and

Subjective equivalence of sinusoidal and random whole-body vibration : M. J. Griffin 1976 Journal of the Acoustical Society of America60, 1140–1145. (6 pages, 4 figures, 3 tables, 12 references)

📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 192 KB

Timing of the back muscle activity evoke

Timing of the back muscle activity evoked by fore-aft sinusoidal and random whole-body vibration: preliminary findings : C. D. Robertson 1988. (10 pages, 2 figures, 1 table, 10 references) (in English)

📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 106 KB