Profesora Verónica Becher.

Horario: Una vez por semana, Lunes de 14 a 18hs

¿Por qué solo la tercera de estas secuencias parece haber sido obtenida tirando una moneda equilibrada?

1111111111111111111111111111111111... todos 1s

010010001000010000010000001000000... bloques incrementales de 0s

00101000100101010000010111110010010...sin patrón

Cuál tiene más información?

Puede una computadora arrojar una secuencia al azar?

Clase introductoria de este curso dictada por Gregory Chaitin en 1998.

Practicas 1,2,3 (azar-1-2-3.pdf).

Practicas 4 a 7 (azar-4-7.pdf).

"Las computadoras libres de prefijos computan lo mismo que las que no lo son" (computadoras-libres-de-prefijos.pdf).

"La aleaoriedad no es recursivamente invariante" (aleat_no_rec_inv.pdf).

"Los numeros reales sin 7s no son aleatorios" (sin7.pdf).

Apunte sobre martingalas (martingalas.pdf).

Programa
1. Repaso de definiciones básicas de la teoría de la computabilidad.

2. Complejidad de largo de programa. Máquinas de Turing autodelimitantes.

3. La desigualdad de Kraft. La relación entre complejidad de largo de programa y probabiliadd algorítmica.

4. La teoría de largo de programa es una medida de entropía de información.

5. ¿Que es aleatoriedad? Definición de Chaitin para numeros reales.

6. El número aleatorio de Chaitin: Omega. Propiedades.

7. Definición de Definición de Martin Löf. Casi todos los números reales son aleatorios.
Equivalencia entre las definiciones de Martin Löf y Chaitin.

8. Números reales computablemente enumerables. Omega es computablemente enumerable.
La clase de los números Omega coincide con la clase de los reales aleatorios computablemente enumerables.

9. Propiedad de Borel normalidad par números reales. Aleatorio implica normal.

10. Jerarquía de aleatoriedad. Otros ejemplos de números aleatorios, más aleatorios que Omega.

11. Aplicaciones de la Teoría de complejidad de largo de Programa.
Distancia (o similaridad) algorítmica. Clasificación de archivos. Otras aplicaciones.

12. Números pseudoaleatorios.

Bibliografia

El trabajo que da origen a la definición matemática de computadora

Alan Turing, "On Computable numbers with an application to the Entscheidungsproblem",
Proceedings of the London Mathematical Society, 2nd Series Vol 42, pp. 230-265, 1936.

Artículo fundamental del la complejidad de largo de programa

Gregory Chaitin, "A theory of program size formally identical to information theory", Journal of the ACM 22, pp. 329-340, 1975

Libros sobre teoría clásica de funciones recursivas

Hartley Rogers Jr. Theory of Recursive Functions and E ective Computability., Cambridge MIT Press, 1967

Piergiorgio Odifreddi, Classical Recursion Theory volume I, volume II", North Holland, Amsterdam, 1992, 1999.

Libros sobre Aleatoriedad

Gregory Chaitin, Algorithmic Information Theory, Cambridge University Press, fourth printing 2003.

Rod Downey, Denis Hirschfeldt. Algorithmic Randomness and Complexity, Springer, 2010

Andre Nies. Computability and Randomness, Oxford University Press, 2009

Ming Li, Paul Vitanyi, Kolmogorov Complexity and Applications, Springer-Verlag, 1997.