¿Supongo que nunca lo sabremos?
– Alan-Turing propuso el TM, que es esencialmente un DFA con una cinta y algunas operaciones (Muy bien, es una tupla de 7). Se puede estudiar como álgebra funcional.
– Lo segundo que hizo fue demostrar que el cálculo Lambda es computacionalmente equivalente a la máquina de Turing . La jerarquía de los lenguajes formales se basa en el reconocimiento y / o la falta del mismo por un TM, un PDA y, por último, un DFA / NFA (en ese orden de disminución de la potencia de cálculo).
Si bien Turing dio un modelo computacional concreto y un resultado correlacionado con los teoremas de incompletitud de Godel (en particular, los teoremas de incompletitud de Gödel) en un entorno práctico a través del teorema de detención , no estoy completamente seguro de que resolver P-NP esté en la misma línea de pensamiento . Computable o no (léase: recursivamente enumerable versus no recursivamente enumerable) no es exactamente lo mismo que polinomio determinista versus polinomio no determinista.
- ¿Cómo detectan las cámaras de vigilancia del aeropuerto un comportamiento sospechoso?
- ¿Cuáles son las ventajas y desventajas de trabajar en una división de investigación frente a una división que no es de investigación en una gran empresa de software?
- ¿Dónde puede encontrar una buena explicación de la gramática libre de contexto?
- ¿Por qué es que 1 byte es igual a 8 bits?
- ¿Cuáles son las mejores cosas que puedo usar la ciencia de datos para investigar?
Mi suposición personal es No , y no creo que Alan Turing hubiera resuelto con éxito el problema P-NP. Alan Turing fundó la Teoría de la Computación (Teoría de la Computabilidad). Sin embargo, a medida que uno estudia más y más, uno ve que P-NP es, estrictamente hablando, un problema en la teoría de la complejidad, que es un poco diferente en términos de objetivos y herramientas que la teoría de la computabilidad.
El tipo de pensamiento en la teoría de la computabilidad y la teoría de la complejidad es un poco diferente. La teoría de la complejidad es un marco genérico para colocar algoritmos de diferentes tipos en una jerarquía. P, NP son marcos de un complejo zoológico de complejidad mucho más grande (Google it). La pregunta P-NP es una cuestión de si dos colecciones de tipos de conjuntos de algoritmos son realmente iguales. La Teoría de la Computabilidad trata más sobre el marco en el cual estos Algoritmos se basarían en términos del costo de las operaciones válidas que usarían, y cuáles son las limitaciones de reconocimiento de Algoritmos dados estas operaciones y el alfabeto.
Para ver la sutil diferencia entre este punto, sugiero leer: Introducción a la teoría de la computación: Michael Sipser: 9781133187790: Amazon.com: Libros
