Aquí hay dos cuestiones separadas a las que Joshua alude en su respuesta.
- ¿Cómo se modelan teóricamente los lanzamientos de monedas en informática?
- ¿Cómo se implementan los lanzamientos de monedas en las computadoras en la práctica?
La respuesta de Joshua Engel aborda bien ambos problemas. Solo tengo algo más que decir sobre el n. ° 1, ya que me parece mucho más interesante que el n. ° 2 y creo que hay preguntas interesantes en esta área que la mayoría de las personas probablemente ni siquiera conocen.
Para el número 1, los informáticos suponen que tienen algún tipo de generador de números aleatorios. En su forma más pura, es simplemente una función de caja negra que escupe un 0 o 1, cada uno con probabilidad 1/2. Cuando se trata de modelos teóricos que usan aleatoriedad, como las máquinas probabilísticas de Turing, simplemente asumimos que la máquina “lanza una moneda” de manera abstracta en cada paso, lo que significa que hace una consulta a esta función aleatoria de caja negra.
- Como una niña india de 23 años, he completado mi licenciatura en tecnología. Me interesa la fotografía y la quiero como mi profesión. ¿Hay alguna forma de convencer a mi papá? ¿Qué tengo que hacer?
- ¿Existe algún modelo de cálculo X más débil que una máquina de Turing (pero aún no trivial) para el cual una máquina de Turing puede predecir el comportamiento de detención?
- ¿Podría alguien explicarme en términos simples el significado de la teoría de la complejidad, la teoría del caos y la teoría de juegos?
- ¿Ya se resolvió P versus NP? ¿Si es así, cómo?
- ¿Cómo se puede diseñar un autómata de estado finito para el siguiente problema?
Para cualquier algoritmo, generalmente nos importa cuánto tiempo y espacio requiere. Otro recurso que es interesante de medir es la cantidad de aleatoriedad que utiliza un algoritmo. La forma estándar de medir la aleatoriedad es el número de lanzamientos de monedas utilizados por el algoritmo o, más precisamente, el número de bits aleatorios. Por ejemplo, un algoritmo determinista usa aleatoriedad cero. Una máquina de Turing probabilística de tiempo polinómico utiliza como máximo aleatoriedad polinómica, ya que lanza como máximo una moneda en cada paso de tiempo, y se ejecuta por un número polinómico de pasos de tiempo.
¿Por qué preocuparse por medir la aleatoriedad? Es posible que haya oído hablar de las clases de complejidad P y BPP . La clase P es todos los lenguajes decidibles por un TM determinista en tiempo polinómico, y se supone que encapsula nuestra noción de “problemas que se pueden resolver de manera eficiente”. Sin embargo, BPP , la clase de lenguajes decidible por un TM probabilístico en tiempo polinómico, es posiblemente un sustituto más razonable para este propósito, ya que en la práctica incluso los algoritmos aleatorios son lo suficientemente buenos.
Obviamente, P está contenido en BPP , ya que uno siempre puede ignorar los lanzamientos de monedas. Intuitivamente, es de esperar que haya problemas que se puedan resolver de manera eficiente utilizando la aleatoriedad, pero no así con algoritmos deterministas. Por ejemplo, la gente solía creer que la prueba de primalidad era un problema. Sin embargo, ahora hay ciertas conjeturas plausibles y ampliamente creídas en la teoría de la complejidad que, de ser ciertas, implicarían P = BPP .
No voy a entrar en los detalles de estas conjeturas, pero permítanme ilustrar una forma realmente ingenua que uno podría aleatorizar BPP . Para mayor precisión, definiré formalmente la clase: BPP es el conjunto de problemas de decisión con una TM probabilística de tiempo polinomial de tal manera que en cada instancia de SÍ, la TM acepta con probabilidad al menos 2/3 (sobre los lanzamientos internos de monedas utilizados en el máquina, no sobre las entradas), y en cada instancia de NO, el TM acepta con probabilidad como máximo 1/3. Ahora, como mencioné anteriormente, tal máquina usa como máximo un número polinómico de lanzamientos de monedas. Suponga que podría mostrar que solo necesita usar O (log n) lanzamientos de monedas. Esto implicaría P = BPP . ¿Cómo es eso? Bueno, si solo usó O (log n) bits aleatorios, podría enumerar todos los 2 ^ O (log n) = n ^ O (1) posibles resultados y contar si acepta al menos 2/3 de los ramas o como mucho 1/3 de ellas!
