Este algoritmo toma como entrada cualquier programa y devuelve una probabilidad de que se detenga.
En el límite de muchos programas, debe responder por término medio en la proporción correcta. Pero estoy interesado en otras condiciones interesantes para un algoritmo exitoso
Hay varias ambigüedades importantes en su pregunta. La forma en que se codifican las máquinas es importante para esto, al igual que el modelo de computación. Además, ¿quieres decir que la máquina siempre se detiene, o que se detiene para una entrada nula? Haré suposiciones razonables para resolver estas ambigüedades, si eso no te sirve tendrás que aclarar tu pregunta.
Supongamos que el modelo computacional es el modelo de máquina de Turing con alfabeto binario de cinta única e infinita. Supongamos que la entrada inicial es cero; una máquina que funcione con una entrada distinta de cero es equivalente a alguna máquina fácilmente identificable con más estados que funcione con una entrada cero, por lo que esta es una suposición razonable. Por último, enumere las máquinas tales que $k<m$ implica una máquina $k$ no tiene más estados que la máquina $m$ no es demasiado restrictivo, ya que se espera que cualquier codificación razonable se acerque lo suficiente a esto para que lo siguiente funcione.
Recientemente se ha demostrado que un programa de tiempo polinómico puede decidir todas las TM excepto una proporción decreciente, véase http://arxiv.org/abs/math/0504351 . Entonces se podría ejecutar este programa y adivinar las máquinas que no puede decidir (o decir que todas se paran o todas no, o lo que sea). Dado que los posibles errores son una proporción decreciente de las entradas, este es el algoritmo que se busca.
El resultado en el que se basa esta respuesta se aplica con cintas y caracteres adicionales en el alfabeto. Creo que todavía no se sabe que se aplique en el caso de la cinta infinita de dos vías. Sin embargo, me parece que es probable que sea así. El documento que he citado lo plantea como una cuestión abierta.
Hacer un promedio de todas las máquinas de Turing posibles (con respecto a alguna medida) es como hacer un promedio de todos los programas escritos por una compañía de monos (sin ánimo de ofender a la especie simia). No es realmente sorprendente que el problema de detención sea fácil para la gran mayoría de ellos.
Bueno, algunos resultados no sorprendentes son extremadamente difíciles de demostrar (por ejemplo, el último teorema de Fermat), por lo que puede ser interesante saber si un resultado esperado se demuestra realmente. También, $P\neq NP$ parece bastante poco sorprendente, pero el resultado más interesante sería si está equivocado. Nunca confíes en una suposición hasta que esté probada, y a veces obtendrás conocimientos sorprendentes.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
2 votos
Relacionados: cstheory.stackexchange.com/questions/2515/
1 votos
Tal vez no sé a qué te refieres con "debe responder en promedio en la proporción correcta", pero esto probablemente depende de la codificación de las máquinas. Por ejemplo, se podría forzar que para cada número que no sea de la forma $2^n$ la máquina con ese código se detiene. Entonces supongo que hay un algoritmo que funciona normalmente. ¿Ves lo que quiero decir?
0 votos
Cualquier algoritmo ciertamente no resolver completamente el problema de Halting (no hay otra probabilidad que $0$ allí). La probabilidad de que un programa dado en una entrada dada se detenga es $0$ o $1$ y encontrar esa probabilidad es lo mismo que decidir si la combinación se detendrá o no. Además, parece bastante inútil obtener la proporción correcta de respuestas si no se atribuyen a las entradas correctas: sería como afirmar en un examen de elección múltiple que, aunque hayas acertado la mayoría de las respuestas, has obtenido la distribución correcta de a/b/c/d. No veo ninguna cuestión razonable en este caso.
0 votos
@Marc van Leeuwen, creo que el OP utiliza el término "proporción" con la intención de dar a entender que la proporción de respuestas incorrectas disminuye a cero a medida que el programa se aplica a todos los enteros bajo un límite creciente. Así que la probabilidad se refiere a la probabilidad de que, bajo algún límite establecido, una respuesta dada sea correcta; y esta probabilidad se limita a 1.
0 votos
@jack: Si el OP se refiere a eso, creo que se debería editar la pregunta para que quede claro.