¿Qué es una buena introducción a las máquinas de turing, la complejidad de las clases, P=NP, etc. desde un punto de vista puramente matemático? Quiero saber la forma de cálculo se refiere a provability en matemáticas, necesito los detalles de cómo uno se relaciona arithemtical declaraciones a máquinas de turing. No, no estoy interesado en la práctica de informática o programación. También quiero saber cómo demostrar que un sistema es turing completo.
Respuestas
¿Demasiados anuncios?
Kekoa
Puntos
11545
Usted puede tratar de Michael Sipser la Introducción a la Teoría de la Computación.
lhf
Puntos
83572
JoshL
Puntos
290
Un buen lugar para comenzar para que la relación entre la computabilidad y provability es la Computabilidad y la Lógica por Boolos, Burgess, y Jeffrey. Pero no es para los débiles de corazón - el contenido es denso, y el libro tiene mucho más contenido que su espesor sugiere.
Para algo más CS centrado que va a tratar de Turing integridad y complejidad, otro gran texto es la Introducción a la Teoría de Autómatas, Lenguajes y Computación por Hopcroft y Ullman. Acaba de saltar capítulos 2-7 que cubren regular y el contexto libre de idiomas. De nuevo, este libro tiene un montón de contenido y está muy bien considerado.
sxd
Puntos
2637
Otro libro muy bueno es de Complejidad Computacional: Un Enfoque Moderno, por Sanjeev Arora. Ver http://www.cs.princeton.edu/theory/complexity/. Es un libro muy bueno y no muy caro en comparación con Sipser y Papadimitriou del libro. Los temas de la portada del libro una variedad de temas en la teoría de la complejidad. También, hay un proyecto en línea, así que usted puede comprobar que si usted quiere ver cómo el libro es como.
