Книга: Этюды для программистов

Литература

Дэвис (Davis M.). Computability and Unsolvability, McGraw-Hill, New York, NY, 1958.

Дэвис приводит с изматывающими подробностями все те доказательства, которые другие авторы «оставляют читателю». Прочитав Дэвиса от корки до корки, вы уже никогда не усомнитесь в справедливости любого утверждения о мощи машины Тьюринга. Впрочем, вполне возможно, что у вас навсегда пропадет охота что бы то ни было слышать об этой машине.

Хопкрофт, Ульман (Hopcroft J. E., Ullman J. D). Formal Languages and Their Relation to Automata. Addison-Wesley, Reading, MA, 1969.

Книга Хопкрофга и Ульмана — наилучший в своей области учебник для аспирантов первого года обучения. В ней содержатся все основные результаты о машинах Тьюринга, причем они излагаются в контексте других классов автоматов Книга полезна также своей обширной библиографией.

Минский (Minsky M. L.). Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs NJ, 1967.

Минский дает прекрасное, легко воспринимаемое введение в теорию автоматов. Это, вероятно, наиболее подходящая книга для первого знакомства с предметом.

* Трахтенброт Б. А. Алгоритмы и вычислительные автоматы. — М.: Советское радио, 1974.

Оглавление книги