¡Podemos!
Hay muchas formas de modificarlo. Muchos de los más naturales dan como resultado modelos de cálculo que en realidad son equivalentes a la máquina de Turing estándar. Por ejemplo, podríamos hacer que la cinta sea “unilateral” (es decir, infinita en una dirección, pero con un punto de detención en la otra). O podríamos agregar dos cintas en lugar de una. O bien, permitimos “0”, “1” y “canguro” como símbolos en lugar de solo “0” y “1”. Todos estos modelos son equivalentes, lo que significa que pueden simularse entre sí, y el conjunto de problemas que pueden resolver son todos iguales.
Hay formas más interesantes de modificar las máquinas de Turing. Por ejemplo, es posible que haya escuchado que una máquina de Turing no puede resolver el problema de detención. Pero, podemos crear un modelo de cómputo en el que una máquina de Turing de otro modo normal tenga acceso a un oráculo al Problema de detención, una caja mágica que siempre devuelve la respuesta al Problema de detención.
- ¿Existe un equivalente al tono perfecto en matemáticas / programación de computadoras? ¿Un atributo que se considera que no se puede aprender pero que es invaluable si lo posee?
- ¿Existe una función que crece más rápido que cualquier función computable, pero que crece a un ritmo fundamentalmente más lento que el de la función Busy Beaver?
- En términos simples, ¿qué es SOCP (programación de cono de segundo orden / programación semi-definida) y en qué se diferencia la optimización convexa de otros tipos de optimizaciones?
- ¿Qué cosas teóricas debo aprender sobre informática?
- ¿Todos los números reales tienen una expansión binaria?
Ahora, tenemos un nuevo modelo de cómputo, que es capaz de determinar si alguna máquina de Turing (ordinaria) se detiene.
(Por supuesto, probablemente no puedas simular tal cosa en la vida real. Oh, bueno).
Podemos crear una jerarquía completa de modelos de computación de esta manera, de máquinas con oráculos que resuelven el problema de detención en el modelo de computación de máquinas con oráculos … Vea el concepto de grado de Turing.
