Artículo
Becher, V.; Figueira, S.; Picchi, R. "Turing's unpublished algorithm for normal numbers" (2007) Theoretical Computer Science. 377(1-3):126-138
Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
In an unpublished manuscript, Alan Turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have Lebesgue measure 1; furthermore, he gave an algorithm for computing instances in this set. We complete his manuscript by giving full proofs and correcting minor errors. While doing this, we recreate Turing's ideas as accurately as possible. One of his original lemmas remained unproved, but we have replaced it with a weaker lemma that still allows us to maintain Turing's proof idea and obtain his result. © 2007 Elsevier Ltd. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | Turing's unpublished algorithm for normal numbers |
| Autor: | Becher, V.; Figueira, S.; Picchi, R. |
| Filiación: | Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Argentina |
| Palabras clave: | Algorithm for normal numbers; Computable absolutely normal numbers; Turing's unpublished manuscript; Error correction; Number theory; Set theory; Theorem proving; Turing machines; Computable construction; Lebesgue measure; Manuscripts; Normal numbers; Algorithms |
| Año: | 2007 |
| Volumen: | 377 |
| Número: | 1-3 |
| Página de inicio: | 126 |
| Página de fin: | 138 |
| DOI: | http://dx.doi.org/10.1016/j.tcs.2007.02.022 |
| Título revista: | Theoretical Computer Science |
| Título revista abreviado: | Theor Comput Sci |
| ISSN: | 03043975 |
| CODEN: | TCSCD |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v377_n1-3_p126_Becher.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v377_n1-3_p126_Becher |
Referencias:
- Ambos-Spies, K., Mayordomo, E., Resource-bounded measure and randomness (1997) Lecture Notes in Pure and Applied Mathematics, pp. 1-47. , Complexity, Logic, and Recursion Theory. Sorbi A. (Ed), Marcel Dekker
- Ambos-Spies, K., Terwijn, S., Zheng, X., Resource bounded randomness and weakly complete problems (1997) Theoretical Computer Science, 172, pp. 195-207
- Bailey, D.H., Crandall, R.E., Random generators and normal numbers (2004) Experimental Mathematics, 11 (4), pp. 527-546
- Becher, V., Figueira, S., An example of a computable absolutely normal number (2002) Theoretical Computer Science, 270, pp. 947-958
- Borel, É., Les probabilités dénombrables et leurs applications arithmétiques (1909) Rendiconti del Circolo Matematico di Palermo, 27, pp. 247-271
- Borel, É., (1914) Leçons sur la thèorie des fonctions. second ed., , Gauthier Villars
- Borel, É., La définition en mathématiques (1998) Les grands courants de la pensèe mathématique, , Le Lionnais F. (Ed), Hermann
- Champernowne, D.G., The construction of decimals in the scale of ten (1933) Journal of the London Mathematical Society, 8, pp. 254-260
- Copeland, A.H., Erdös, P., Note on normal numbers (1946) Bulletin American Mathematical Society, 52, pp. 857-860
- Harman, G., (1998) London Mathematical Society Monographs, 18. , Oxford University Press
- Harman, G., One hundred years of normal numbers (2002) Number Theory for the Millennium, 2, pp. 149-166. , Millennial Conference on Number Theory. Bennett M.A., Brendt B.C., Boston N., Diamond H.G., Hildebrand A.J., and Philipp W. (Eds), A. K. Peters
- Kuipers, L., Niederreiter, H., (1974) Uniform Distribution of Sequences, , Wiley Interscience, New York
- Sierpiński, W., Démonstration élémentaire du théorème de M. Borel sur les nombres absolument normaux et détermination effective d'un tel nombre (1917) Bulletin de la Société Mathématique de France, 45, pp. 127-132
- Turing, A.M., A note on normal numbers (1992) Collected Works of A.M. Turing: Pure Mathematics, pp. 117-119. , Britton J.L. (Ed), North Holland, Amsterdam
Citas:
---------- APA ----------
Becher, V., Figueira, S. & Picchi, R. (2007) . Turing's unpublished algorithm for normal numbers. Theoretical Computer Science, 377(1-3), 126-138.http://dx.doi.org/10.1016/j.tcs.2007.02.022
---------- CHICAGO ----------
Becher, V., Figueira, S., Picchi, R. "Turing's unpublished algorithm for normal numbers" . Theoretical Computer Science 377, no. 1-3 (2007) : 126-138.http://dx.doi.org/10.1016/j.tcs.2007.02.022
---------- MLA ----------
Becher, V., Figueira, S., Picchi, R. "Turing's unpublished algorithm for normal numbers" . Theoretical Computer Science, vol. 377, no. 1-3, 2007, pp. 126-138.http://dx.doi.org/10.1016/j.tcs.2007.02.022
---------- VANCOUVER ----------
Becher, V., Figueira, S., Picchi, R. Turing's unpublished algorithm for normal numbers. Theor Comput Sci. 2007;377(1-3):126-138.http://dx.doi.org/10.1016/j.tcs.2007.02.022
