Un secreto a voces en ciencias de la computación es que todos los idiomas en los que programa no son Turing Complete.
La integridad de Turing permite la ejecución de cualquier algoritmo definible, dada una cantidad de almacenamiento arbitrariamente grande (algunos dicen infinito).
Por lo tanto, si bien su programa puede verse en una versión ideal platónica de C, Java, Python o cualquier otra cosa, que es Turing Complete, el lenguaje implementado tiene una restricción que impide que sea así en lo que generalmente se considera una manera trivial. Si su programa requiere billones de líneas de código, buena suerte para obtener un compilador para manejarlo, básicamente.
De manera similar, ocasionalmente tropezará con un lenguaje de secuencias de comandos patentado que solo ha contado (es decir, bucles similares) y sin subrutinas. Si no hay forma de “repetir hasta que se termine”, desaparece una enorme clase de algoritmos.
Además de restricciones artificiales como esa, vale la pena considerar que un curso de Teoría de la Computación lo guiará esencialmente a través de cuatro “niveles” de computación.
- Un autómata de estado finito (máquina de estado) puede pasar de su estado actual a un conjunto finito de otros estados basándose en la prueba de una condición.
- Un autómata pushdown (máquina de pila) es el mismo, excepto que agrega la parte superior de una pila a la decisión del siguiente estado, y la acción en cada estado puede incluir empujar o saltar desde dicha pila.
- Un autómata con límites lineales convierte la pila en una cinta de longitud arbitraria / infinita, pero restringe la capacidad de escribir en alguna región específica.
- Una máquina de Turing elimina la restricción de escritura.
Hay un par de otras máquinas intercaladas y es posible que haya visto un modelo similar con gramáticas regulares, sin contexto, sensibles al contexto y sin restricciones, que son equivalentes. Puede ver el conjunto completo en varios campos en una práctica tabla en la parte inferior de la página de Wikipedia del autómata Pushdown o cualquier página similar.
En general, si restringe un idioma de una manera no trivial (como poner un límite en el espacio de almacenamiento máximo), empujará el idioma a un modelo de nivel inferior.