Abstract:
Using possibly infinite computations on universal monotone Turing machines, we prove Martin-Löf randomness in ø′ of the probability that the output be in some set script O sign ⊆ 2≤ω under complexity assumptions about script O sign. © 2005, 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., Grigorieff, S., Recursion and topology on 2≤ω for possibly infinite computations (2004) Theoretical Computer Science, 322, pp. 85-136
- Random Reals and Possibly Infinite Computations. Part II: Higher Order Randomness, , In preparation
- Wadge Reducibility and Spectral Continuous Maps into 2 ≤ω, , In preparation
- Boasson, L., Nivat, M., Adherences of languages (1980) Journal of Computer and System Sciences, 20, pp. 285-309
- Calude, C., (1994) Information and Randomness, , Springer
- Calude, C.S., Hertling, P.H., Khoussainov, B., Wang, Y., Recursively enumerable reals and Chaitin Ω numbers (1998) STACS 98 (Paris, 1998), (1373), pp. 596-606. , Lecture Notes in Computer Science, Springer-Verlag
- 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
- Algorithmic entropy of sets (1976) Computers & Mathematics with Applications, 2, pp. 233-245. , Available on Chaitin's home page
- (1987) Algorithmic Information Theory, 1st Ed., , Cambridge University Press
- Downey, R., (2000) Some Computability-theoretical Aspects of Reals and Randomness, , Notes from lectures given at the University Notre Dame. Available at MSCS, University of Wellington, NZ
- Downey, R., Hirschfeldt, D., (2004) Algorithmic Randomness and Complexity, , Springer, To appear. Preliminary version, November 30th , available on Downey's home page
- Downey, R., Hirschfeldt, D., Nies, A., Randomness, computability and density (2002) SIAM Journal on Computing, 31, pp. 1169-1183. , Extended abstract in Proceedings of the STAGS 2001, LNCS 2010
- Downey, R., Laforte, G.L., Presentations of computably enumerable reals (2002) Theoretical Computer Science, 284 (2), pp. 539-555
- Head, T., The adherences of languages as topological spaces (1985) Automata and Infinite Words, 192, pp. 147-163. , (M. Nivat and D. Perrin, editors). Lecture Notes in Computer Science
- The topological structure of adherence of regular languages (1986) RAIRO, Theoretical Informatics and Applications, 20, pp. 31-41
- Kechris, A.S., (1995) Classical Descriptive Set Theory, , Springer
- Levin, L., On the notion of random sequence (1973) Soviet Math. Dokl., 14 (5), pp. 1413-1416
- Li, M., Vitanyi, P., (1997) An Introduction to Kolmogorov Complexity and Its Applications, 2d Ed., , Springer
- Martin-Löf, P., The definition of random sequences (1966) Information and Control, 9, pp. 602-619
- Miller, J., Personal communication; Moschovakis, Y.N., (1980) Descriptive Set Theory, , North Holland
- Muchnik, An.A., Personal communication; Odifreddi, P., (1989) Classical Recursion Theory, 125. , Studies in Logic, North-Holland
- 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
- Schnorr, C.P., Process complexity and effective random tests (1973) Journal of Computer and System Sciences, 7, pp. 376-388
- A survey of the theory of random sequences (1977) Basic Problems in Methodology and Linguistics, pp. 193-210. , (R. E. Butts and J. Hintikka, editors), D. Reidel
- Soare, R., Recursion theory and Dedekind cuts (1969) Transactions of the American Mathematical Society, 140, pp. 271-294
- Solovay, R.M., (1975) Draft of a Paper (or a Series of Papers) on Chaitin's Work, , Unpublished manuscript, IBM Research Center, NY
- On random R.E. Sets (1977) Non-classical Logics, Model Theory and Computability, pp. 283-307. , (A. I. Arruda, N. C. A. da Costa, and R. Chuaqui, editors), North-Holland
- Turing, A., On computable numbers, with an application to the Entscheidungsprohlem (1936) Proceedings of the London Mathematical Society, 2nd Series, 42, pp. 230-265. , Correction, Ibid., vol. 43 (1937) pp. 544-546
- Wadge, W.W., Degrees of complexity of subsets of the Baire space (1972) Notices of the American Mathematical Society, pp. A-714
- (1984) Degrees of Complexity of Subsets of the Baire Space, , Ph.D. thesis, University of Berkeley
Citas:
---------- APA ----------
Becher, V. & Grigorieff, S.
(2005)
. Random reals and possibly infinite computations part I: Randomness in ø′. Journal of Symbolic Logic, 70(3), 891-913.
http://dx.doi.org/10.2178/jsl/1122038919---------- CHICAGO ----------
Becher, V., Grigorieff, S.
"Random reals and possibly infinite computations part I: Randomness in ø′"
. Journal of Symbolic Logic 70, no. 3
(2005) : 891-913.
http://dx.doi.org/10.2178/jsl/1122038919---------- MLA ----------
Becher, V., Grigorieff, S.
"Random reals and possibly infinite computations part I: Randomness in ø′"
. Journal of Symbolic Logic, vol. 70, no. 3, 2005, pp. 891-913.
http://dx.doi.org/10.2178/jsl/1122038919---------- VANCOUVER ----------
Becher, V., Grigorieff, S. Random reals and possibly infinite computations part I: Randomness in ø′. J. Symb. Logic. 2005;70(3):891-913.
http://dx.doi.org/10.2178/jsl/1122038919