Turing potencia completa y computacional

En una conferencia, un profesor mencionó que las computadoras modernas no tienen tanta potencia computacional como una máquina de Turing porque no tienen memoria infinita, y dado que ninguna computadora puede tener memoria infinita, la máquina de Turing es inalcanzable y simplemente representa el límite superior de informática. ¿Existe una medida o definición de qué problemas (o clase de problemas) quedan fuera del alcance de nuestra potencia informática debido a esto?

Si pensamos en el universo como finito, cualquier cosa que necesite más memoria que esa cantidad finita está más allá de nuestra capacidad computacional.

Sin embargo, este no es un buen modelo para estudiar la computabilidad, el modelo de máquina de Turing funciona mucho mejor en realidad y esa es la razón por la que lo usamos para estudiar la computación en computadoras reales. Una máquina de Turing realmente no necesita una cantidad infinita de memoria, solo necesita una cantidad ilimitada de memoria. Por ejemplo, podemos proporcionar memoria adicional a una computadora con el tiempo (ya que la computadora necesita más y más memoria) y luego tenemos algo similar a una máquina Turing. Si suponemos que tenemos una cantidad ilimitada de tiempo y memoria para terminar nuestro cálculo, entonces la máquina Turing captura este concepto de computabilidad en principio bastante bien.

Consulte el artículo de Wikipedia sobre las máquinas de Turing, hay una sección que analiza la relevancia del modelo.

Si está interesado en la computabilidad factible , entonces la teoría de la complejidad (donde consideramos una cantidad variada de recursos como el tiempo y el espacio para realizar una tarea computacional) está más cerca de lo que realmente podemos hacer en la práctica que la teoría de la computabilidad. Muchos expertos afirman que los cálculos factibles caen en la clase de complejidad (y más recientemente en versiones probabilísticas y cuánticas de , es decir, y ).$\mathsf{P}$$\mathsf{P}$$\mathsf{BPP}$$\mathsf{BQP}$

Puede considerar que el autómata lineal limitado y los idiomas correspondientes son lenguajes sensibles al contexto . Consulte la Jerarquía de Chomsky para saber qué idiomas están fuera del alcance de dichos autómatas.

Por cierto, en cierto sentido, algunos problemas "inalcanzables" ahora están al alcance, ¡debido a la potencia informática restringida!

Por ejemplo, el problema de detención para máquinas de Turing es indecidible, pero es decidible para autómatas lineales delimitados.

La teoría de la computación es una abstracción del mundo real. En muchos sentidos, la abstracción no se ajusta muy bien al mundo real. Por un lado, no podemos hacer computadoras con memoria ilimitada; así que ni siquiera podemos hacer máquinas para reconocer lenguajes regulares arbitrarios, ¡o incluso lenguajes finitos arbitrarios!

Sin embargo, esto no resulta ser un problema demasiado grande; En el mundo real, ni siquiera podemos construir entradas de cualquier tamaño arbitrario, e incluso si pudiéramos, no estaríamos lo suficientemente cerca como para ver la respuesta.

En un sentido estricto, entonces, no: la clase de computadoras físicamente realizables es estrictamente menos poderosa que la clase de máquinas Turing. También es estrictamente menos potente que la clase de autómatas finitos.