Abstract:
We obtain a large class of significant examples of n-random reals (i.e.. Martin-Löf random in oracle Ø (n-1) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set @ ⊆ B (N). In particular, we develop methods to transfer ∑ n 0 or Π n 0 many-one completeness results of index sets to n-randomness of associated probabilities. © 2009, Association for Symbolic Logic.
Referencias:
- BECHER, V., CHAITIN, G., Another example of higher order randomness (2002) Fundamenta Informaticae, 51 (4), pp. 325-338
- BECHER, V., CHAITIN, G., DAICZ, S., A highly random number (2001) Proceedings of the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS'01), pp. 55-68. , C.S. Calude, M.J. Dineen, and S. Sburlan, editors, Springer-Verlag
- BECHER, V., FIGUEIRA, S., GRIGORIEFF, S., MILLER, J.S., Randomness and halting probabilities (2006) this JOURNAL, 71 (4), pp. 1411-1430
- BECHER, V., GRIGORIEFF, S., Recursion and topology on 2 ≤ω for possibly infinite computations (2004) Theoretical Computer Science, 322, pp. 85-136
- BECHER, V., GRIGORIEFF, S., Random reals and possibly infinite computations. Part 1: Randomness in Ø l (2005) this JOURNAL, 70 (3), pp. 891-913
- BECHER, V., GRIGORIEFF, S., Random reals à la Chaitin with no prefix-freeness (2007) Theoretical Computer Science, 385, pp. 193-201
- (2008) Randomness and Outputs in a computable ordered set (Random reals and possibly infinite computations: Part III), , in preparation
- C.S. CALUDE, P.H. HERTLING, and B. KHOUSSAINOV Y. WANG, Recursively enumerable reals and Chaitin Ω numbers, Stacs 98 (Paris, 1998), Lecture Notes in Computer Science, 1373, Springer-Verlag, 1998, pp. 596-606; CHAITIN, G., A theory of program size formally identical to information theory (1975) Journal of the ACM, 22, pp. 329-340. , Available on Chaitin's home page
- DOWNEY, R., HIRSCHFELDT, D., (2008) Algorithmic randomness and complexity, , Springer, to appear
- HJORTH, G., NIES, A., Randomness via effective descriptive set theory (2007) The Journal of the London Mathematical Society, 75 (2), pp. 495-508
- KREISEL, G., SHOENFIELD, J.R., WANG, H., Number theoretic concepts and recursive wett-orderings, Archiv fur math (1960) Logik und Grundlagenforschung, 5, pp. 42-64
- ROGERS, H., (1967) Theory of recursive functions and effective computability, , McGraw-Hill
- SACKS, G.E., (1966) Degrees of unsolvability, Annals of Mathematical Studies, , Princeton University Press
- SCOTT, D.S., Continuous lattices (1972) Lecture Notes in Math, 2, pp. 97-136. , Toposes, algebraic geometry analogic RW. Lawvered, editor, Springer
- SELIVANOV, V.L., Hierarchies in φ-spaces and applications (2005) Mathematical Logic Quaterly, 51 (1), pp. 45-61
- SOARE, R., (1986) Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, , Springer
- STILLWELL, J., Decidability of the almost all theory of degrees (1972) this JOURNAL, 37, pp. 501-506
- WADGE, W.W., Degrees of complexity of subsets of the Baire space (1972) Notices of the American Mathematical Society, pp. A-714
Citas:
---------- APA ----------
Becher, V. & Grigorieff, S.
(2009)
. From index sets to randomness in Ø n: Random reals and possibly infinite computations part II. Journal of Symbolic Logic, 74(1), 124-156.
http://dx.doi.org/10.2178/jsl/1231082305---------- CHICAGO ----------
Becher, V., Grigorieff, S.
"From index sets to randomness in Ø n: Random reals and possibly infinite computations part II"
. Journal of Symbolic Logic 74, no. 1
(2009) : 124-156.
http://dx.doi.org/10.2178/jsl/1231082305---------- MLA ----------
Becher, V., Grigorieff, S.
"From index sets to randomness in Ø n: Random reals and possibly infinite computations part II"
. Journal of Symbolic Logic, vol. 74, no. 1, 2009, pp. 124-156.
http://dx.doi.org/10.2178/jsl/1231082305---------- VANCOUVER ----------
Becher, V., Grigorieff, S. From index sets to randomness in Ø n: Random reals and possibly infinite computations part II. J. Symb. Logic. 2009;74(1):124-156.
http://dx.doi.org/10.2178/jsl/1231082305