Es difícil definir cuál es el programa más básico, pero creo que la función de identidad es un buen candidato. Un programa que asigna cada entrada a sí mismo, sin alterar ([matemática] f (x) = x [/ matemática]) sigue siendo un programa, tan simple como es.
El programa más complicado también es difícil de definir, y el hecho de que haya una escalera infinita de algoritmos cada vez más complicados complica aún más las cosas, pero creo que también tengo un buen candidato (o conjunto de candidatos). Sin embargo, la explicación requiere cierto conocimiento de los resultados básicos de la teoría de la computabilidad.
Desde Turing, sabemos que hay problemas indecidibles . En pocas palabras, un problema indecidible es uno para el que hay instancias que no puede resolver en un tiempo finito, sin importar cuán inteligente sea su algoritmo o poderoso su mecanismo de computación. El ejemplo canónico de un problema indecidible es el problema de detención, que pregunta si una máquina de Turing determinada se detiene o no, dada una entrada específica. Es fácil ver por qué este problema es indecidible, ya que si no lo fuera, podríamos construir programas paradójicos. Puede construir una máquina de Turing que 1) decida si alguna otra máquina de Turing se detiene si recibe alguna información, y 2) se ejecuta para siempre si se detiene y se detiene si no lo hace. Entonces podrías alimentar a esta máquina de Turing consigo misma, y sucede algo extraño. Podría detenerse, lo que significa que funcionaría para siempre, pero también podría funcionar para siempre, lo que significa que se detendría. Esta es una versión computacional de la “paradoja del mentiroso”, en la que alguien dice “Esta oración es una mentira” y no hay ningún valor de verdad que pueda atribuirle sin entrar en una paradoja.
- Según usted, ¿cuáles son los algoritmos de aprendizaje automático más importantes en la actualidad?
- ¿Cuáles son algunos libros que debe leer un experto en algoritmos?
- ¿Qué tipo de datos debo usar en C para almacenar datos como a1b2c3? ¿Podría usar una matriz de caracteres para almacenar esto como una cadena?
- ¿Qué algoritmo de aprendizaje automático es mejor para agrupar pequeños cuerpos de texto por tema / categoría?
- ¿Explicar diferentes algoritmos de ruta más corta, sus restricciones, complejidades?
Ahora considere el problema de contar cuántos pasos tiene la máquina de Turing de mayor duración y tamaño [math] N [/ math] (como en: la TM tiene [math] N [/ math] estados) antes de detenerse. Este problema es claramente indiscutible, ya que le pide que decida qué TM se detienen y cuáles no. El problema de detención, que es indecidible, es un subproblema de este. La secuencia de cuántos pasos experimentan las TMs de detención más duraderas, para un número creciente de estados, se conoce como la secuencia Busy Beaver, y aunque el problema de calcular un número Busy Beaver es en sí indecidible, pudimos calcular los primeros cuatro elementos de la secuencia usando argumentos matemáticos inteligentes. Podemos calcular algunos de ellos, pero la indisputabilidad del problema subyacente significa que solo podemos hacerlo un número finito de veces. Existe un límite, por grande que sea, para el mayor número de Busy Beaver que podamos calcular.
Adam Yedidia y Scott Aaronson proporcionaron recientemente un límite superior a este límite: 7918. Lo que hicieron fue desarrollar una máquina Turing de estado 7918 que “probaría” todos los teoremas derivados de ZFC (el sistema axiomático en la base de las matemáticas modernas), y detenerse solo si se encuentra una inconsistencia. Kurt Gödel demostró que ningún sistema axiomático puede demostrar su propia consistencia, lo que significa que es imposible demostrar que esta máquina de Turing no se detendrá. Esperamos que no se detenga, porque esperamos que nuestro sistema axiomático sea consistente, pero finalmente no podemos probarlo. Como resultado, no podemos calcular el Busy Beaver del 7918, ni ninguno de los BB (infinitos) que lo siguen.
No afirmo que este TM es el programa más complicado jamás escrito (ciertamente no lo es), pero su comportamiento es infinitamente complejo, hasta el punto de que nuestro sistema axiomático (nuestras matemáticas) no tiene remedio para analizarlo. No hay trucos inteligentes, ni teoremas, nada que podamos usar para tratar de adivinar si se detendrá o no.
