Texto de teoría de la recursión, alternativa a Soare

Question

Me quiere/necesita para aprender algo de la teoría de la recursividad, equivalente aproximadamente a las partes a y B de Soare del texto. Esto cubre "postgrado básico material", hasta el Post del problema, oracle construcciones, y el finito lesión prioridad método. Hay una alternativa, más fácil para principiantes versión de este material en otro texto? (En aproximadamente senior de pregrado o de postgrado a partir del nivel de dificultad, aunque yo no necesariamente mente más fácil.)

Por ejemplo, uno de los textos que he visto es S. Barry Cooper del libro, la Teoría de la Computabilidad. Hay alguien que se ha de leer esta y Soare, y podría decirme acerca de sus similitudes y diferencias?

Answer 1

Usted está en una difícil situación: usted está interesado en el material que generalmente se enseña en el nivel de postgrado, pero quiere un libro escrito en un nivel inferior. Eso es un problema común para los estudiantes en matemáticas, y usualmente no hay solución fácil. La mayoría de pregrado a nivel de libros sobre la computabilidad sólo ir a través de la detención de problema, y luego se detiene. Cutland del libro de texto, que creo que es un muy buen libro de pregrado, es un ejemplo de esto.

Soare el libro es el libro de texto estándar en la computabilidad en el momento (si es que existe tal cosa como un libro de texto estándar). Es un principio de posgrado a nivel de libro, lo que significa que no requiere de ningún conocimiento previo de la computabilidad, sólo una gran inversión de esfuerzo para aprender el material. La mayoría de los volúmenes de nivel de posgrado se requiere de una cuidadosa lectura y la relectura, junto con ejercicios de trabajo, para aprender el material. Eso es simplemente la manera en que las cosas son.

Cooper del libro está escrito de una manera que hace que el material se siente mucho más accesibles, como un avanzado nivel de pregrado. Creo que hace un buen trabajo de presentación de la forma en que la computabilidad de los teóricos de pensar acerca de la zona, y el libro tiene una mayor selección de los temas que en otros libros escritos en un nivel similar. Sin embargo, esta omitiendo muchos detalles, que tendrían que trabajar por ti mismo. Hay un riesgo, con libros de este tipo, que puede tener una falsa confianza en su comprensión del material. Soare del libro es mucho más exigente con respecto a los detalles. En la final, el uso de Cooper del libro se requieren tanto esfuerzo como Soare el libro, excepto a los que habría que trabajar en los detalles de la prueba por ti mismo.

Mi recomendación sería la de lee Cooper del libro para tener una idea de lo que está pasando, y para tener una idea general, luego de cavar en Soare del libro para aprender las pruebas en detalle.

También hay un texto clásico por Rogers, que es bien considerado. Aunque el libro es un poco viejo, el material de la computabilidad y la prioridad de los argumentos está muy bien escrito y perfectamente aplicables hoy en día.

Answer 2

Sólo para mencionar, Enderton ha publicado recientemente un libro llamado la Teoría de la Computabilidad. No he leído, así que no sé cómo es.

También Odiffredi ha escrito Clásica de la Teoría de la Recursividad Volumen 1 y 2. Estos dos enormes libro contiene más material del que cualquier otro libro de texto en la Teoría de la Computabilidad. También como una enciclopedia. Nunca lo he usado como libro de texto, pero es muy bueno para la referencia - usted puede aprender acerca de Quasicreastive conjuntos de aquí. En términos de temas, creo que tiene incluso una mayor diversidad de temas que Cooper. Sólo mirar en la tabla de contenido que vea las cosas como probabalistic física, el equipo y el pensamiento, el cerebro, .... Volumen II, incluso hace algunos teoría de la complejidad.

También, en mi opinión, la teoría de la Computabilidad es más que el aprendizaje de algunos resultados. Un montón de Computabilidad Teoría es acerca de los diversos métodos (lo que permite, finito de la lesión, infinito lesión, un árbol, etc) de la construcción de varios tipos o grados. La parte del libro que usted menciona (hasta finito de la lesión) es bastante bueno para aprender a hacer estas construcciones. Trabajando pensamiento Soares del libro y hacer los ejercicios es una buena forma de entender estos método de construcción lo suficientemente bien como para ser capaz de hacer uno usted mismo.

Answer 3

Para una introducción aceleró para arriba, usted podría intentar 'Teoría de la computación' por Dexter Kozen. Conferencias 33 adelante parece en alguna teoría de la recursión, por lo que puede ayudarle a sentirse cómodo con las cosas antes de empezar con las cosas más pesadas. Aunque es posible que no cubra todo el material que buscas (no con el detalle suficiente en cualquier caso). Pero todavía, es una lectura agradable, y también hay algunos ejercicios agradables al final.

Answer 4

He encontrado el video conferencias que se impartieron en la Universidad de Colorado en Boulder, en la Primavera de 2011 por Bart Kastermans. El plan de estudios incluye el material que usted ha mencionado y:

Lección 24 Finito lesión, mostrando la existencia de un bajo simple conjunto.

Lección 27 Infinito de la Lesión y el Espesor de la Lema.

Lección 31 De Densidad Teorema De

Para una persona que aprende por sí sola, es útil para ver cómo otros matemáticos el tratamiento de los conceptos, de ahí que los videos pueden ser un buen complemento para el material de aprendizaje. Para 0"' prioridad método, Soare es todavía la mejor fuente.

Answer 5

Un libro de texto introductorio popular que cubre la computabilidad y la complejidad es "Introducción a la teoría de computación" de Michael Sipser. La sección de computabilidad concluye con un capítulo bonito en temas avanzados de computabilidad.