Tenía exactamente la misma pregunta cuando tomé Automata Theory. Mis profesores me dijeron que no se podía hacer, pero obstinado mocoso que era, me dispuse a intentarlo.
Lo que finalmente concluí fue que la reducción de Turing a DFA solo se puede realizar en caso de que la cinta sea finita. Esto me permitirá construir un DFA con un número finito de estados. Han pasado algunos años, por lo que mi recuerdo de los cálculos exactos que realicé puede ser defectuoso, pero lo que finalmente llegué a la conclusión es que incluso para el idioma más simple posible: uno que tiene solo 1 letra y una longitud máxima de palabra n (es decir, longitud de cinta n), necesita al menos n estados para representar todas las palabras posibles. Esto aumenta exponencialmente con el número de letras. Las lenguas que se ajustan a algunos criterios específicos no soportan pensar en este contexto.
Esto anula el propósito de la máquina Turing, que tiene la cinta infinita como su característica más poderosa. Aparentemente, esto podría usarse en ciertas situaciones, cuando desee reducir la complejidad de un problema, en caso de que esté absolutamente seguro de los límites de la cinta, pero esa es una situación en gran medida hipotética. Es mejor atenerse a las máquinas genéricas.
- ¿Por qué los sistemas P no implican que P = NP?
- ¿Cuál es el papel de las matemáticas en las computadoras?
- Cómo implementar esto en Python: dada una matriz, encuentre tres números a, byc de modo que a ^ 2 + b ^ 2 = c ^ 2
- ¿Cuáles son los problemas finales más interesantes del cálculo?
- ¿Por qué 0.8 * 3 devuelve 2.4000000000000004 en lugar de 2.4?
