La programación interactiva o en tiempo real se puede realizar en máquinas RAM, lo que la hace ‘computable’ en una máquina Turing.
Lo primero que debe darse cuenta es que una máquina de Turing no es una máquina real. Es un ‘modelo informático’. Por lo tanto, el modelo de Turing (o el marco como lo dice) es más apropiado. Un modelo de Turing tiene tres piezas.
- 1) Un mecanismo de cinta de almacenamiento secuencial, que es infinito
- 2) Un número fijo de estados para cada registro (activado, desactivado, por ejemplo) y
- 3) Una lectura-escritura y un puntero de transición: una forma de moverse de un registro (ubicación) a otro.
- Las máquinas informáticas actuales están basadas principalmente en RAM. Los modelos informáticos basados en RAM contrastan con los modelos informáticos de Turing. Una diferencia es que la recuperación (y colocación) casi instantánea de los contenidos de RAM hace que el puntero de transición (una característica clave de una máquina de Turing) no tenga sentido.
Sin embargo, una máquina de acceso aleatorio ha demostrado ser teóricamente equivalente a una máquina de Turing.
- ¿Cómo la inteligencia artificial cambiará los mercados de valores en el futuro?
- ¿Cómo calculo un "Probabilidad de pertenecer al género XYZ" -Score para pistas de música usando WEKA?
- ¿Hay alguna manera de decidir si una simulación perfecta de todos los aspectos de su estado mental es realmente consciente?
- ¿Hay alguna evidencia de que la Singularidad Tecnológica ha comenzado a surgir?
- ¿Cuál tiene mejor alcance? ¿AI o red informática y valores?
La cinta en las máquinas de Turing es secuencial, mientras que las computadoras reales tienen memoria de acceso aleatorio. Para implementar dicha capacidad de RAM, las máquinas Turing se aumentan con registros adicionales para contener las direcciones reales de las ubicaciones de la cinta. Entonces, con los registros adicionales, una TM puede actuar como una máquina RAM.
La programación interactiva o en tiempo real se puede realizar en máquinas RAM, lo que la hace ‘computable’ en una máquina Turing.
Aquí hay un buen video de YouTube sobre el tema.
Una pregunta relacionada es ¿Son las máquinas de Turing ‘cuánticas’ equivalentes a las máquinas de Turing ‘clásicas’?
La respuesta es un poco complicada, porque aunque son COMPUTACIONALMENTE equivalentes (una computadora clásica PUEDE simular cualquier cálculo cuántico), no son similares desde el punto de vista de la teoría de la COMPLEJIDAD. Es decir: los QC pueden resolver varios problemas (como factorizar números grandes) en tiempo polinómico (en marcos de tiempo razonables), mientras que las máquinas Turing clásicas no pueden.
Entonces, desde el punto de vista de la teoría de la complejidad, una máquina Quantum Turing es superior a una máquina clásica de Turing. Desde un simple punto de vista “computacional”, se puede demostrar que son equivalentes.
