В университете на лекциях о машине Тьюринга рассказывали мало и непонятно. Мне нужна была какая-нибудь дополнительная литература на эту тему. Попалась эта книга.
Операции над машинами Тьюринга, теория NP-полноты, информация про то, что программа имеет вид таблицы, определенный алгоритм или нет - это все есть в книге, с примерами. Изложение конечно академическое, с формулами, но для серьезного глубокого погружения в тему идеально подходит.
«Математическая машина Тьюринга и вычислительная сложность» kitobiga sharhlar