×

From index sets to randomness in \(\emptyset ^{n}\): Random reals and possibly infinite computations. II. (English) Zbl 1163.03023

[For Part I see J. Symb. Log. 70, No. 3, 891–913 (2005; Zbl 1089.03037).]
The paper constructs a significant class of examples of \(n\)-random reals which are probabilities that a universal monotone Turing machine performing possibly infinite computations on infinite inputs produces an output in a given set.

MSC:

03D80 Applications of computability and recursion theory
03D10 Turing machines and related notions
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)

Citations:

Zbl 1089.03037
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1145/321892.321894 · Zbl 0309.68045
[2] Algorithmic randomness and complexity (2008)
[3] Randomness and Outputs in a computable ordered set (Random reals and possibly infinite computations: Part III) (2008)
[4] DOI: 10.1016/j.tcs.2007.06.007 · Zbl 1124.68046
[5] Random reals and possibly infinite computations. Part I: Randomness in ’ 70 pp 891– (2005) · Zbl 1089.03037
[6] DOI: 10.1016/j.tcs.2004.03.026 · Zbl 1061.03075
[7] Randomness and halting probabilities 71 pp 1411– (2006)
[8] Proceedings of the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS’01) pp 55– (2001)
[9] Fundamenta Informaticae 51 pp 325– (2002)
[10] Notices of the American Mathematical Society pp A– (1972)
[11] Decidability of the almost all theory of degrees 37 pp 501– (1972)
[12] Recursively enumerable sets and degrees (1986) · Zbl 0401.03018
[13] DOI: 10.1002/malq.200310126 · Zbl 1058.03048
[14] Toposes, algebraic geometry and logic 2 pp 97– (1972)
[15] Degrees of unsolvability (1966)
[16] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[17] DOI: 10.1007/BF01977642 · Zbl 0129.00402
[18] DOI: 10.1112/jlms/jdm022 · Zbl 1118.03034
[19] DOI: 10.1007/BFb0028594
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.