Generador de números verdaderamente aleatorio: ¿Turing computable?

Estoy buscando una respuesta definitiva sobre si la generación de números "verdaderamente aleatorios" es computable por Turing. No sé cómo expresar esto con precisión. Esta pregunta de StackExchange sobre "algoritmos eficientes para la generación de números aleatorios" se acerca a responder mi pregunta. Charles Stewart dice en su respuesta: "[la aleatoriedad de Martin-Löf] no puede ser generada por una máquina". Ross Snider dice que "cualquier proceso determinista (como Turing / Register Machines) no puede producir números aleatorios 'filosóficos' o 'verdaderos'". ¿Existe una noción clara y aceptada de lo que constituye un generador de números verdaderamente aleatorio? Y si es así, ¿se sabe que una máquina de Turing no puede calcularlo?

Quizás señalarme la literatura relevante sería suficiente. ¡Gracias por cualquier ayuda que usted nos pueda proporcionar!

Editar. ¡Gracias a Ian y Aaron por las respuestas informadas! Estoy relativamente sin estudios en esta área, y estoy agradecido por la ayuda. Si puedo extender un poco la pregunta en este apéndice: ¿Es el caso que una TM con acceso a una fuente pura de aleatoriedad (¿un oráculo?), Puede calcular una función que una TM clásica no puede?

Me estoy uniendo a la discusión bastante tarde, pero trataré de abordar varias preguntas que se hicieron anteriormente.

Primero, como lo observó Aaron Sterling, es importante decidir primero qué queremos decir con números "verdaderamente aleatorios", y especialmente si estamos viendo las cosas desde una perspectiva computacional de complejidad o computabilidad.

Permítanme sostengo sin embargo, que en la teoría de la complejidad, la gente está interesada principalmente en seudo -randomness y seudo generadores -RANDOM, es decir, las funciones de las cadenas a cadenas de tal manera que la distribución de las secuencias de salida no se puede decir aparte de la distribución uniforme por algunos eficiente proceso de (donde se pueden considerar varios significados de eficiente , por ejemplo, polytime computable, circuitos de tamaño polinómico, etc.). Es un área de investigación hermosa y muy activa, pero creo que la mayoría de la gente estaría de acuerdo en que los objetos que estudia no son realmente aleatorios, es suficiente que solo se vean aleatorios (de ahí el término "pseudo").

En la teoría de la computabilidad, ha surgido un consenso sobre lo que debería ser una buena noción de "aleatoriedad verdadera", y de hecho es la noción de aleatoriedad de Martin-Löf la que prevaleció (se han propuesto otras y son interesantes de estudiar, pero no lo muestran todo) las buenas propiedades que tiene la aleatoriedad de Martin-Löf). Para simplificar las cosas, consideraremos la aleatoriedad para secuencias binarias infinitas (otros objetos tales como funciones de cadenas a cadenas pueden codificarse fácilmente por dicha secuencia).

Una secuencia binaria infinita es aleatoria de Martin-Löf si ningún proceso computable (incluso si permitimos que este proceso sea computable en un tiempo exponencial triple o superior) puede detectar una falla de aleatoriedad.$\alpha$

(1) ¿Qué queremos decir con "defecto de aleatoriedad"? Esa parte es fácil: es un conjunto de medida 0, es decir, una propiedad que casi todas las secuencias no tienen (en este caso podemos hablar de una medida de Lebesgue es decir, la medida en que cada bit tiene un probabilidad de ser 0 independiente de todos los demás bits) Un ejemplo de tal falla es "tener asintóticamente 1/3 de ceros y 2/3 de unos", lo que viola la ley de los grandes números. Otro ejemplo es "por cada n, los primeros 2n bits de α están perfectamente distribuidos (tantos ceros como unos)". En este caso, la ley de los grandes números está satificada, pero no el teorema del límite central. Etcétera etcétera.$1/2$$0$$\alpha$
(2) ¿Cómo puede un proceso computable probar que una secuencia no pertenece a un conjunto particular de medida 0? En otras palabras, ¿qué conjuntos de medida 0 se pueden describir de manera computable? Esto es precisamente de lo que se tratan las pruebas de Martin-Löf. Una prueba de Martin-Löf es un procedimiento computable que, dada una entrada k, de manera computacional (es decir, a través de una máquina Turing con entrada ) genera una secuencia de cadenas w k , 0 , w k , 1 , ... tal que el conjunto U k de secuencias infinitas comenzando por una de esas w k , tengo medida como máximo 2 - $k$$w_{k,0}$$w_{k,1}$$U_k$$w_{k,i}$$2^{-k}$(si le gusta la topología, observe que este es un conjunto abierto en la topología del producto para el conjunto de secuencias binarias infinitas). Entonces el conjunto tiene la medida 0 y se conoce como Martin-Löf nullset . Ahora podemos definir la aleatoriedad de Martin-Löf diciendo que una secuencia binaria infinita α es aleatoria de Martin-Löf si no pertenece a ningún conjunto nulo de Martin-Löf . $G=\bigcap_k U_k$$0$$\alpha$

Esta definición puede parecer técnica, pero se acepta ampliamente como la correcta por varias razones:

• es lo suficientemente eficaz, es decir, su definición implica procesos computables
• es lo suficientemente fuerte: cualquier propiedad "casi segura" que pueda encontrar en un libro de texto de teoría de probabilidad (ley de grandes números, ley de logaritmo iterado, etc.) puede probarse mediante una prueba de Martin-Löf (aunque esto a veces es difícil de probar)
• varias personas lo han propuesto de forma independiente utilizando diferentes definiciones (en particular, la definición de Levin-Chaitin utilizando la complejidad de Kolmogorov); y el hecho de que todos conducen al mismo concepto es una pista de que debería ser la noción correcta (un poco como la noción de función computable, que se puede definir a través de máquinas Turing, funciones recursivas, cálculo lambda, etc.)
• ¡La teoría matemática detrás de esto es muy buena! ver los tres excelentes libros Introducción a la complejidad de Kolmogorov y sus aplicaciones (Li y Vitanyi), Aleatoriedad y complejidad algorítmica (Downey y Hirschfeldt) Computabilidad y aleatoriedad (Nies).

¿Cómo es una secuencia aleatoria de Martin-Löf? Bueno, toma una moneda perfectamente equilibrada y comienza a lanzarla. En cada vuelta, escriba un 0 para caras y un 1 para colas. Continuar hasta el final de los tiempos. Así es como se ve una secuencia de Martin-Löf :-)

Ahora volvamos a la pregunta inicial: ¿hay una manera computable de generar una secuencia aleatoria de Martin-Löf? Intuitivamente, la respuesta debería ser NO , porque si podemos usar un proceso computable para generar una secuencia , entonces ciertamente podemos usar un proceso computable para describir el singleton { α }, entonces α no es aleatorio. Formalmente esto se hace de la siguiente manera. Supongamos que una secuencia α es computable. Considere la siguiente prueba de Martin-Löf: para todos los k , simplemente envíe el prefijo a k de α de longitud k , y nada más. Esto tiene una medida como máximo (de hecho, exactamente) 2 - $\alpha$$\alpha$$\alpha$$\alpha$$k$$a_k$$\alpha$$k$$2^{-k}$, y la intersección de los conjuntos como en la definición es exactamente { α }. QED !!$U_k$${\alpha}$

De hecho, una secuencia aleatoria de Martin-Löf es incuestionable en un sentido mucho más fuerte: si algún cálculo de oráculo con oráculo β (que en sí mismo es una secuencia binaria infinita) puede calcular α , entonces para todos los n , n - O ( 1 ) bits de Se necesitan β para calcular los primeros n bits de α (esto es, de hecho, una caracterización de la aleatoriedad de Martin-Löf, que desafortunadamente rara vez se menciona como en la literatura).$\alpha$$\beta$$\alpha$$n$$n-O(1)$$\beta$$n$$\alpha$

Ok, ahora la parte "editar" de la pregunta de Joseph: ¿Es el caso de que una TM con acceso a una fuente pura de aleatoriedad (¿un oráculo?), Puede calcular una función que una TM clásica no puede?

Desde una perspectiva de computabilidad, la respuesta es "sí y no". Si se le da acceso a una fuente aleatoria como un oráculo (donde la salida se presenta como una secuencia binaria infinita), con probabilidad 1 obtendrá un oráculo aleatorio Martin-Löf, y como vimos anteriormente, Martin-Löf random implica no- computable, por lo que es suficiente para generar el oráculo mismo! O si desea una función , puede considerar la función f que, para todo n, le dice cuántos ceros hay entre los primeros n bits de su oráculo. Si el oráculo es aleatorio de Martin-Löf, esta función no será computable.$f: \mathbb{N} \rightarrow \mathbb{N}$$f$$n$$n$

Pero, por supuesto, podría argumentar que esto es trampa: de hecho, para un oráculo diferente podríamos obtener una función diferente, por lo que hay un problema de no reproducibilidad. Por lo tanto, otra forma de entender su pregunta es la siguiente: ¿existe una función que no sea computable, pero que pueda "computarse con probabilidad positiva", en el sentido de que hay una máquina de Turing con acceso a un oráculo aleatorio que, con probabilidad positiva (sobre el oráculo), calcula f . La respuesta es no, debido a un teorema de Sacks cuya prueba es bastante simple. En realidad, todo ha sido respondida por Robin Kothari: si la probabilidad para la TM sea correcta es mayor que 1/2, entonces uno puede mirar para todos n en todos los cálculos posibles de entrada del oráculo con $f$$f$$n$$n$y encuentre el resultado que obtiene el "voto mayoritario", es decir, que es producido por un conjunto de oráculos de medida de más de la mitad (esto se puede hacer de manera efectiva). El argumento incluso se extiende a probabilidades más pequeñas: suponga que la TM produce con probabilidad ϵ > 0 . Según el teorema de densidad de Lebesgue, existe una cadena finita σ tal que si fijamos que los primeros bits del oráculo sean exactamente σ , y luego obtengamos los otros bits al azar, entonces calculamos f con probabilidad de al menos 0.99. Al tomar tal σ , podemos aplicar el argumento anterior nuevamente.$f$$\epsilon >0$$\sigma$$\sigma$$f$$\sigma$

Hay (quizás) una distinción que debe hacerse entre "Turing computable" y "efectivamente computable" para responder a su pregunta. Si uno define "proceso aleatorio" como "un proceso que no se puede predecir, sin importar los recursos que tengamos", y uno define "proceso determinista" como "proceso predecible, dada la entrada y el acceso a (tal vez muchos) recursos, "entonces ninguna función computable de Turing puede ser aleatoria, porque si conocemos la máquina de Turing y la simulamos, siempre podríamos predecir el resultado del próximo" experimento "del proceso.

En este marco, una prueba de Martin-Lof puede verse como un proceso determinista, y la definición de una secuencia aleatoria es precisamente una secuencia cuyo comportamiento no se predice por ninguna prueba de Martin-Lof / proceso computacional / determinista de Turing.

Sin embargo, esto plantea la pregunta: "¿Es una secuencia aleatoria efectivamente calculable, en la vida real?" De hecho, hay una industria aquí. Hay CD publicados con miles de millones de bits aleatorios (?) Que se utilizan para realizar simulaciones por computadora de sistemas físicos, etc. Estos CD garantizan que sus secuencias de bits pasan un montón de pruebas de Martin-Lof. El libro The Drunkard's Walk: How Randomness Rules our Lives da una explicación pop-sci de este tema, con mayor detalle.

Punto irrelevante: Disfruto de tu columna. :-)

Intuitivamente, "aleatorio" significa "impredecible", y cualquier secuencia generada por una máquina de Turing puede predecirse ejecutando la máquina, por lo que las máquinas de Turing no pueden producir números "verdaderamente aleatorios". Hay una serie de definiciones formales de secuencias aleatorias (la aleatoriedad solo tiene sentido ya que la longitud de una cadena llega al infinito), todas las cuales son esencialmente equivalentes. Quizás el más natural de estos es la aleatoriedad de Martin-Lof, lo que significa que una secuencia pasa todas las pruebas estadísticas computables posibles de estocasticidad, y la aleatoriedad de Chaitin, lo que significa que todas las subsecuencias iniciales son incompresibles (más específicamente, tienen una alta complejidad de Kolmogorov). En ambas definiciones, es incuestionable generar secuencias aleatorias y reconocerlas. Ver el libro "Información y aleatoriedad:

Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado. Porque, como se ha señalado varias veces, no existe un número aleatorio: solo hay métodos para producir números aleatorios, y un procedimiento aritmético estricto, por supuesto, no es tal método. - John von Neumann

Parece que nadie ha respondido a su apéndice, así que voy a intentarlo:

Si puedo extender un poco la pregunta en este apéndice: ¿Es el caso que una TM con acceso a una fuente pura de aleatoriedad (¿un oráculo?), Puede calcular una función que una TM clásica no puede?

Voy a tratar de hacer la pregunta más precisa y luego responderla. (Sin embargo, mi versión podría no ser lo que tenía en mente, así que avíseme si no lo es).

Tenemos una TM determinista con acceso a un generador de números aleatorios. Esta TM ahora calcula alguna función (una función real, es decir, un mapa determinista de un espacio de entrada a un espacio de salida) haciendo uso del generador de números aleatorios de alguna manera.

Entonces, ¿está permitido que la TM con acceso a la aleatoriedad cometa un error? De lo contrario, el DTM debe dar la respuesta correcta sin importar qué bits aleatorios se suministren. En este caso, los bits aleatorios son innecesarios, ya que podría tomar la cadena aleatoria como 00000 ...

$f_i(x,r)$$f_i$$r$

Con respecto a su "pregunta de edición": hace una gran diferencia si está preguntando sobre la computabilidad o la complejidad. Si hay límites de complejidad en la TM, entonces obtiene el llamado modelo de oráculo aleatorio . Si la TM puede usar recursos arbitrariamente grandes pero finitos, entonces estás en el mundo de la aleatoriedad relativa : hay jerarquías de oráculos de aleatoriedad, al igual que los grados de Turing. (Punto secundario: una de las (in) famosas críticas de Koblitz y Menzes fue sobre el uso del modelo de oráculo aleatorio, por lo que su meta-pregunta es conmovedora en debates académicos recientes).

Todavía estoy tratando de entender tu pregunta modificada, especialmente qué límites colocas en la TM. Entonces, aunque esta respuesta podría no obtener exactamente lo que desea, tal vez ayude un poco a reducir las cosas.

Sabemos que hay un resultado de imposibilidad incondicional para aproximar con un factor subexponencial el volumen de un cuerpo convexo de manera determinista (este es un viejo resultado de Bárány y Füredi ). Por el contrario, podemos obtener un FPRAS para este problema mediante el muestreo. ¿Es este un ejemplo de la separación que estás buscando?