Artículo
Becher, V.; Chaitin, G. "Another example of higher order randomness" (2002) Fundamenta Informaticae. 51(4):325-338
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability β that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the second jump of the halting problem. Indeed, we prove that β is exactly as random as the halting probability of a universal machine equipped with an oracle for the second jump of the halting problem, in spite of the fact that β is defined without considering oracles.
Registro:
| Documento: | Artículo |
| Título: | Another example of higher order randomness |
| Autor: | Becher, V.; Chaitin, G. |
| Filiación: | Departamento de Computación, Ciudad Universitaria, Universidad de Buenos Aires, Pabellón I, 1428 Buenos Aires, Argentina IBM Thomas J. Watson Res. Center, P O Box 218, Yorktown Heights, NY 10598, United States |
| Palabras clave: | Infinite computations; Program size complexity; Randomness; Algorithms; Computational complexity; Computer program listings; Computer simulation; Probability; Problem solving; Finite size complexity; Random processes |
| Año: | 2002 |
| Volumen: | 51 |
| Número: | 4 |
| Página de inicio: | 325 |
| Página de fin: | 338 |
| Título revista: | Fundamenta Informaticae |
| Título revista abreviado: | Fundam Inf |
| ISSN: | 01692968 |
| CODEN: | FUINE |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01692968_v51_n4_p325_Becher |
Referencias:
- Becher, V., Daicz, S., Chaitin, G., A highly random number (2001) Combinatorics, Computability and Logic: 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 London
- Calude, C., (1994) Information and Randomness. An Algorithmic Perspective, , Springer-Verlag, Berlin
- Calude, C.S., Nies, A., Chaitin Ω numbers and strong reducibilities (1997) J. UCS, 3, pp. 1161-1166
- Calude, C., A characterization of c.e. random reals (2002) Theoretical Computer Science, 271 (1-2), pp. 3-14
- Chaitin, G.J., A theory of program size formally identical to information theory (1975) J. ACM, 22, pp. 329-340
- Chaitin, G.J., Algorithmic entropy of sets (1976) Computers & Mathematics with Applications, 2, pp. 233-245
- Chaitin, G.J., (1987) Algorithmic Information Theory, , Cambridge University Pres, Cambridge
- Chaitin, G.J., (2001) Exploring Randomness, , Springer-Verlag, London
- Ferbus-Zanda, M., Grigorieff, S., Is randomness "native" to computer science?. Logic in computer science column (2001) Bulletin of EATCS, 74, pp. 78-118
- Kraft, L.G., (1949) A device for quantizing, grouping and coding amplitude modulated pulses, , Master'S thesis, Dept. of Electrical Engineering, M.I.T., Cambridge, Massachusets
- Odifreddi, P.G., (1989) Classical Recursion Theory, 1. , North Holland, Amsterdam
- Shoenfield, J.R.M., Recursion theory (1993) Lecture Notes in Logic, 1. , reprinted, A.K. Peters, Ltd
- Soare, R., Recursion theory and Dedekind cuts (1969) Trans. Amer. Math. Soc., 140, pp. 271-294
- Solovay, R.M., 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 Publishing Company
- Turing, A., On computable numbers, with an application to the Entscheidungsproblem (1936) Proceedings of the London Mathematical Society, 2nd series, 42, pp. 230-265
Citas:
---------- APA ----------
Becher, V. & Chaitin, G. (2002) . Another example of higher order randomness. Fundamenta Informaticae, 51(4), 325-338.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01692968_v51_n4_p325_Becher [ ]
---------- CHICAGO ----------
Becher, V., Chaitin, G. "Another example of higher order randomness" . Fundamenta Informaticae 51, no. 4 (2002) : 325-338.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01692968_v51_n4_p325_Becher [ ]
---------- MLA ----------
Becher, V., Chaitin, G. "Another example of higher order randomness" . Fundamenta Informaticae, vol. 51, no. 4, 2002, pp. 325-338.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01692968_v51_n4_p325_Becher [ ]
---------- VANCOUVER ----------
Becher, V., Chaitin, G. Another example of higher order randomness. Fundam Inf. 2002;51(4):325-338.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01692968_v51_n4_p325_Becher [ ]
