Si elimina la cinta infinita de una máquina de Turing, obtendrá una máquina de estado finito o un autómata de estado finito. Los idiomas reconocidos por un FSM son exactamente los idiomas regulares, lo que desafortunadamente excluye muchos idiomas interesantes. (Pero incluye interesantes como “todos los números primos hasta un número muy grande”).
Una traducción literal del problema P vs NP en autómatas finitos: ¿hay lenguajes que sean reconocibles por un FSM no determinista en transiciones polinomiales de muchos estados que no sean aceptados por un FSM determinista en transiciones polinomialmente de muchos estados? Desafortunadamente, esto no tiene sentido porque cualquier lenguaje normal puede ser aceptado en O (n) tiempo. Sin embargo, tenemos un resultado básico que dice que cualquier FSM no determinista puede traducirse en uno determinista (a costa de una explosión exponencial en el número de estados).
Ahora, no estamos acostumbrados a FSM con un número inimaginablemente grande de estados. Por ejemplo, una computadora con 2 GB de memoria tiene más de [matemáticas] 2 ^ {2 ^ {20}} [/ matemáticas], aproximadamente [matemáticas] 10 ^ {315652} [/ matemáticas]. Pero eso es “todo” lo que tiene, por lo que cualquier lenguaje no regular eventualmente contendrá alguna palabra demasiado grande para ser reconocida.
- ¿Los usuarios de Quora usarían Dice.com para encontrar un trabajo tecnológico?
- ¿Cómo genera música la computadora? ¿Qué sucede dentro de la computadora para generar música?
- ¿Cuál es la mejor práctica para 'portar' modelos de Machine Learning (especialmente aprendizaje profundo) de Python a sistemas integrados para aplicaciones como visión artificial?
- ¿Cuál es la mejor transmisión para ir en el presente, Mainframe o .Net?
- ¿Apagar el protector contra sobretensiones después de apagar la computadora dañará la computadora a largo plazo?
Más fructífero, podría considerar PSPACE, el conjunto de todos los problemas resueltos utilizando solo un polinomio de almacenamiento en el tamaño de la entrada. Esto podría verse como una máquina Von Neumann equipada con memoria “suficientemente grande” para el problema de interés: cuanto mayor es el tamaño del problema, más memoria. Pero PSPACE contiene NP, por lo que volvemos al problema normal de P vs. NP.
