“The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field--the Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.”

http://en.wikipedia.org/wiki/P_%3D_NP_problem

P vs NP Problem

http://www.claymath.org/millennium/P_vs_NP/

http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

Ray Solomonoff

http://world.std.com/~rjs/index.html

“Founder of algorithmic probability theory & universal theory of inductive inference. First to encounter the concept of Kolmogorov complexity, and first to prove the celebrated invariance theorem”

http://www.idsia.ch/~juergen/ray.html

Solomonoff Homepage

http://world.std.com/~rjs/index.html

La información y el azar. Números casuales

Por Verónica Engler (Centro de Divulgación Científica - FCEyN)

Noticias Breves de la FCEyN, Miércoles 3 de marzo de 2004

"Recién en los años 60 se consiguió formalizar una definición matemática del azar, fue dada al mismo tiempo por dos investigadores: uno fue Per Martin Löf, un discípulo de Andrei Kolmogorov (uno de los teóricos más importantes de la Teoría de las Probabilidades), y el otro fue un investigador que se llama Gregory Chaitin"

http://web.fcen.uba.ar/prensa/noticias/2004/noticias_03mar_2004.html

Complejidad de Kolmogorov

http://la-coliflor.blogspot.com/2007/06/complejidad-de-kolmogorov.html

Kolmogorov complexity

http://en.wikipedia.org/wiki/Kolmogorov_complexity

Turing en una cáscara de nuez: Complejidad de Kolmogorov

http://singularidad.wordpress.com/2007/06/28/turing-en-una-cascara-de-nuez-complejidad-de-kolmogorov/

Gregory Chaitin

http://es.wikipedia.org/wiki/Gregory_Chaitin

Omega: un número que desafía las leyes de la matemática

http://www-2.dc.uba.ar/profesores/becher/lanacion.pdf

Turing en una cáscara de nuez: castores afanosos y la paradoja de Berry

http://singularidad.wordpress.com/2007/05/15/turing-en-una-cascara-de-nuez-castores-afanosos-y-la-paradoja-de-berry/

Función castor afanoso (busy beaver en inglés)

“que podemos definir informalmente como el mayor valor que un algoritmo de cierto tamaño puede producir.”

http://singularidad.wordpress.com/2007/05/15/turing-en-una-cascara-de-nuez-castores-afanosos-y-la-paradoja-de-berry/

Constante de Chaitin

“La constante de Chaitin es un número entre 0 y 1. Es la probabilidad que un programa elegido al azar detenga correctamente a una máquina de Turing determinada.

Sea P el conjunto de todos los programas que se detienen, y |p| el tamaño en bits de un programa p, Ω está definida de la siguiente manera:

Esta constante no es computable. Es posible conocer los primeros decimales, pero a partir de cierto decimal (que depende de la codificación elegida) no es posible saber más decimales.”

http://es.wikipedia.org/wiki/Constante_de_Chaitin

Chaitin's constant

“In the computer science subfield of algorithmic information theory a Chaitin constant or halting probability is a real number that informally represents the probability that a randomly-chosen program will halt. These numbers are formed from a construction due to Gregory Chaitin.

Although there are infinitely many halting probabilities, it is common to use the letter Ω to refer to them as if there were only one. Because Ω depends on the program encoding used, it is sometimes called Chaitin's construction instead of Chaitin's constant when not referring to any specific encoding.

Each halting probability is a normal and transcendental real number which is definable but not computable, which means that there is no halting algorithm that enumerates its digits.”

http://en.wikipedia.org/wiki/Chaitin%27s_constant

Maestría en Dinámica no Lineal y Sistemas Complejos

Grupo de Discusión UNAM-UCM Universidad de la Ciudad de México

Diciembre de 2002

http://sirena.fciencias.unam.mx/ucm.html/maestro/

Instituto de Sistemas Complejos de Valparaíso (ISCV)

http://www.iscv.cl/

Electronic Colloquium on Computational Complexity ECCC

"The Electronic Colloquium on Computational Complexity is a new forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The purpose of this Colloquium is to use electronic media for scientific communication and discussions in the computational complexity community."

http://eccc.hpi-web.de/

Electronic Colloquium on Computational Complexity

Wikipedia (20140401)

"The Electronic Colloquium on Computational Complexity (ECCC) is an electronic archive of research papers in computational complexity theory, a branch of computer science"

http://en.wikipedia.org/wiki/Electronic_Colloquium_on_Computational_Complexity