Artículo

Becher, V. "Turing's normal numbers: Towards randomness" (2012) Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012. 7318 LNCS:35-45
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In a manuscript entitled "A note on normal numbers" and written presumably in 1938 Alan Turing gave an algorithm that produces real numbers normal to every integer base. This proves, for the first time, the existence of computable normal numbers and it is the best solution to date to Borel's problem on giving examples of normal numbers. Furthermore, Turing's work is pioneering in the theory of randomness that emerged 30 years after. These achievements of Turing are largely unknown because his manuscript remained unpublished until its inclusion in his Collected Works in 1992. The present note highlights Turing's ideas for the construction of normal numbers. Turing's theorems are included with a reconstruction of the original proofs. © 2012 Springer-Verlag.

Registro:

Documento: Artículo
Título:Turing's normal numbers: Towards randomness
Autor:Becher, V.
Ciudad:Cambridge
Filiación:Departamento de Computación, Facultad de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, (1428) Buenos Aires, Argentina
Palabras clave:Normal numbers; Real number; Number theory; Random processes; Computability and decidability
Año:2012
Volumen:7318 LNCS
Página de inicio:35
Página de fin:45
DOI: http://dx.doi.org/10.1007/978-3-642-30870-3_5
Título revista:Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7318LNCS_n_p35_Becher

Referencias:

  • Becher, V., Figueira, S., Picchi, R., Turing's unpublished algorithm for normal numbers (2007) Theoretical Computer Science, 377, pp. 126-138
  • 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, , 2nd edn., Gauthier Villars
  • Bugeaud, Y., Nombres de Liouville et nombres normaux (2002) Comptes Rendus de l'Académie des Sciences de Paris, 335, pp. 117-120
  • Bugeaud, Y., (2012) Distribution Modulo One and Diophantine Approximation, , Cambridge University Press
  • Bourke, C., Hitchcock, J., Vinodchandran, N., Entropy rates and finite-state dimension (2005) Theoretical Computer Science, 349 (3), pp. 392-406
  • Chaitin, G., A theory of program size formally identical to information theory (1975) Journal ACM, 22, pp. 329-340
  • Cassels, J.W.S., On a paper of Niven and Zuckerman (1952) Pacific Journal of Mathematics, 2, pp. 555-557
  • Downey, R., Hirschfeldt, D., (2010) Algorithmic Randomness and Complexity, , Springer
  • Downey, R., Randomness, Computation and Mathematics (2012) LNCS, 7318, pp. 163-182. , Cooper, S.B., Dawar, A., Löwe, B. (eds.) CiE 2012. Springer, Heidelberg
  • Hardy, G.H., Wright, E.M., (1938) An Introduction to the Theory of Numbers, , 1st edn. Oxford University Press
  • Harman, G., (1998) Metric Number Theory, , Oxford University Press
  • Kučera, A., Slaman, T., Randomness and recursive enumerability (2001) SIAM Journal on Computing, 31 (1), pp. 199-211
  • Kuipers, L., Niederreiter, H., (2006) Uniform Distribution of Sequences, , Dover
  • Lebesgue, H., Sur certaines d'emonstrations d'existence (1917) Bulletin de la Société Mathématique de France, 45, pp. 132-144
  • Levin, M.B., On absolutely normal numbers (1979) Moscow University Mathematics Bulletin, 34, pp. 32-39. , English translation in
  • Dai, L., Lutz, J., Mayordomo, E., Finite-state dimension (2004) Theoretical Computer Science, 310, pp. 1-33
  • Martin-Löf, P., The Definition of Random Sequences (1966) Information and Control, 9 (6), pp. 602-619
  • Nies, A., (2009) Computability and Randomness, , Oxford University Press
  • Schnorr, C.-P., Zufälligkeit und Wahrscheinlichkeit (1971) Lecture Notes in Mathematics, 218. , Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. Springer, Berlin
  • Schnorr, C.-P., Stimm, H., Endliche Automaten und Zufallsfolgen (1972) Acta Informatica, 1, pp. 345-359
  • 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., On computable numbers, with an application to the Entscheidungsproblem (1936) Proceedings of the London Mathematical Society Series 2, 42, pp. 230-265
  • Turing, A.M., A note on normal numbers (1992) Collected Works of A.M. Turing: Pure Mathematics, pp. 263-265. , Britton, J.L. (ed.) North Holland, Amsterdam with notes of the editor in 263-265
  • Schmidt, W.M., On normal numbers (1960) Pacific Journal of Math., 10, pp. 661-672
  • Strauss, M., Normal numbers and sources for BPP (1997) Theoretical Computer Science, 178, pp. 155-169A4 - Association for Symbolic Logic; Cambridge University Press; Elsevier B.V.; European Association for Computer Science Logic (EACSL); International Federation for Computational Logic (IFCoLog)

Citas:

---------- APA ----------
(2012) . Turing's normal numbers: Towards randomness. Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, 7318 LNCS, 35-45.
http://dx.doi.org/10.1007/978-3-642-30870-3_5
---------- CHICAGO ----------
Becher, V. "Turing's normal numbers: Towards randomness" . Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 7318 LNCS (2012) : 35-45.
http://dx.doi.org/10.1007/978-3-642-30870-3_5
---------- MLA ----------
Becher, V. "Turing's normal numbers: Towards randomness" . Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, vol. 7318 LNCS, 2012, pp. 35-45.
http://dx.doi.org/10.1007/978-3-642-30870-3_5
---------- VANCOUVER ----------
Becher, V. Turing's normal numbers: Towards randomness. Lect. Notes Comput. Sci. 2012;7318 LNCS:35-45.
http://dx.doi.org/10.1007/978-3-642-30870-3_5