¿Nuestra PC funciona como máquina de Turing? El modelo de una máquina de Turing consiste en una cinta de memoria infinita, que significa estados infinitos. Pero supongamos que si nuestra PC tiene 128 MB de memoria y 30 GB de disco, tendría 256 ^ 30128000000 estados y, por lo tanto, tiene estados finitos.
Sé que podemos escribir un tipo de programa que, si durante la ejecución nos quedamos sin memoria, solicitará cambiar el disco de memoria con un disco de memoria vacío y reanudar la ejecución.
Pero, ¿qué pasa si no intercambiamos el disco de memoria, en este caso, es correcto considerar la PC como FA ?
Respuestas:
Tienes razón en que las computadoras físicas tienen memoria finita y, por lo tanto, no están completas para Turing. Hay otras formas en que la teoría de la computabilidad no es un buen modelo para la computación: no tiene en cuenta las limitaciones de tiempo y memoria. La teoría de la complejidad se inventó (tal vez) como una descripción más realista de la informática, pero en mi humilde opinión, tiene problemas similares (pero más sutiles).
Por otro lado, para estudiar matemáticamente las capacidades y los límites de la informática, necesitamos usar alguna abstracción que no tenga restricciones. Eso hace posible el análisis. De manera similar, en mecánica estadística suponemos que el número de elementos (átomos o moléculas) es tan grande que el comportamiento está cerca del límite (es decir, dejamos que el número de elementos tienda al infinito). Estudiar informática desde una perspectiva asintótica tiene ventajas similares, pero a veces es engañoso. Aquí hay algunos ejemplos de esto último:
Otro problema es que las computadoras reales no funcionan en absoluto como las máquinas de Turing. Funcionan como máquinas RAM, que son una mejor abstracción para la informática real.
fuente
Creo que ya has dado la respuesta tú mismo. Si el aspecto principal que le preocupa es la (in) finidad de los estados, entonces una Máquina de Turing como tal solo existe como "un dispositivo hipotético".
No importa cuánta memoria le dé a su PC, siempre será limitada, por lo tanto, puede encontrar un programa que se ejecutará en una máquina Turing "real", pero no en esta PC debido a la cinta delimitada.
http://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines
fuente
Cuando se inventaron las máquinas de Turing, las computadoras eran mujeres que realizaban cálculos en papel de desecho. Esa es la noción de computación de las máquinas de Turing express. Su cinta no es parte de ellos, como tampoco lo es el papel de desecho es parte de una persona que realiza cálculos.
Este sigue siendo un buen modelo para el cálculo basado en computadora porque los límites de los recursos en las computadoras generalmente son bastante grandes. Los modelos de cálculo inherentemente finitos solo se vuelven útiles cuando el número de estados posibles es muy pequeño.
fuente
Una computadora moderna está completa, generalmente este término se usa con la excepción del dispositivo de almacenamiento infinito. En la práctica, la memoria puede ser bastante larga. Por ejemplo, además de ser aproximadores de funciones universales, se dice que las redes neuronales recurrentes con memoria (y que se ejecutan repetidamente) están completas. De hecho, las máquinas de Neural Turing llevan esta idea a una etapa más profunda, deduciendo algoritmos simples.
fuente