¿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?

Si entiendo su pregunta, está postulando la existencia de una máquina más básica que una máquina de Turing, pero aún capaz de manejar problemas computacionales generalizados. Además, creo que no está preguntando sobre el problema de detención, sino sobre la predicción del comportamiento de esa máquina que postuló.

¡Uf! Eso fue un bocado! También es una pregunta fascinante.

Toda mi capacitación formal en ciencias de la computación fue como ingeniero, por lo que tendió a centrarse en el lado práctico de las cosas. Si recuerdo mis cursos correctamente, me dijeron que una máquina de Turing es la máquina teórica más simple que calificó como una computadora general, es decir, una que no está especializada para un pequeño conjunto de problemas. Si eso es correcto, entonces la respuesta a su pregunta debe ser “no”.

Pero, todavía me pregunto. He implementado máquinas de estado finito (FSM) que se detendrán de manera confiable en determinadas condiciones. Por “alto”, me refiero a entrar en un estado terminal que solo puede dejarse reiniciando el FSM. Eso plantea (al menos) dos preguntas:

1. ¿Se puede calcular el comportamiento de detención de todos los FSM?
2. Si es así, ¿es este FSM “generalizado” demasiado trivial para calificar como su “máquina de Turing débil?”

Lamento que esto no responda a tu pregunta, pero estoy pensando de todos modos porque es muy fascinante.

¡Bien, compañeros coroanos! ¡Hazlo e iluminame! (Er, por favor!)

Hay varios modelos de computación que siempre se detendrán (autómatas finitos, autómatas pushdown, funciones recursivas primitivas …). Esos definitivamente no son triviales.

También puede usar un autómata lineal, que es esencialmente una máquina de Turing con una cinta finita en lugar de una cinta infinita. A veces se repite para siempre, pero el número total de estados de cálculo (posición de la cabeza * cadenas en la cinta) es fácil de calcular. Por lo tanto, puede ejecutarlo hasta que sepa que la cantidad de pasos es mayor que la cantidad de estados posibles. En ese punto, si no se ha detenido, sabrá que debe haber repetido un estado, por lo que continuará en ese ciclo para siempre.

Parece haber una correlación muy fuerte entre “comportamiento interesante” (“máquina útil”) y “comportamiento caótico” (“comportamiento complejo”). Se utiliza al describir la vida, los ecosistemas, la actividad cerebral consciente, la sociedad, la economía. Aparece en los sets de Mandelbrot y Conway’s Game of Life. Supongamos (sin ninguna prueba real) que las máquinas de Turing son interesantes por exactamente la misma razón.

Si su pregunta hubiera sido sobre el Juego de la vida de Conway (que se puede usar para implementar una Máquina universal de Turing), entonces no, no creo que ningún ajuste a las reglas del juego conduzca a otra cosa que no sea un comportamiento aburrido. Pero está muy cuantizado; o la regla es que la celda central se enciende si está rodeada por 3 celdas encendidas, o bien 2 o 4, no hay posibilidad de que 3.123456789 sean la prueba.

Sospecho que esto también será lo que frustrará su búsqueda en el caso de la Máquina de Turing: el umbral entre ser una Máquina de Turing Universal y no ser una Máquina de Turing Universal está demasiado cuantizado. (Del mismo modo, entre ser incompleto / inconsistente para Gödel y ser completo y consistente).

Dicho esto, es posible que pueda escribir sus ecuaciones de estado para su Máquina universal de Turing en la forma, x_ {n + 1} = r * x_ {n} * (1 – x_ {n}), que permite un total elección continua de valores para “r”. ¡Buena suerte en esta investigación! ¡Espero sinceramente leer sobre sus resultados!

Una máquina de Turing puede determinar si una máquina de estado finito se detendrá, porque todas las máquinas de estado finito se detendrán.

Una máquina de Turing puede determinar si cierto autómata de empuje se detendrá, porque todos los autómatas de empuje se detendrán.

Ofreceré una concurrencia parcial a Timothy Johnson. Para las máquinas de Turing con cintas de longitud finita, puede (en teoría) enumerar todas las máquinas posibles y determinar empíricamente si se detiene o no. La “predicción” se convierte en encontrar el resultado en una tabla de búsqueda.

Creo que los autómatas de estados finitos y los autómatas pushdown calificarían, y ciertamente no son “trivialmente débiles”.