Книга по теоретической информатике - не найти...

[Mathdream]

Здравствуйте. Посоветуйте, пожалуйста, книгу по теоринформатике, где подробно с доказательствами описывались бы основы - машины Тьюринга, классы сложности, теория вычислимости, проблема остановки, сведения по Левину, по Карпу, по Тьюрингу... По этим сведениЯм, кстати, даже в интернете мало информации.

Заранее благодарю, и, если у Вас есть ссылка на электронный вариант книг, то укажите, пожалуйста.

[Mathdream]

Здравствуйте. Посоветуйте, пожалуйста, книгу по теоринформатике, где подробно с доказательствами описывались бы основы - машины Тьюринга, классы сложности, теория вычислимости, проблема остановки, сведения по Левину, по Карпу, по Тьюрингу... По этим сведениЯм, кстати, даже в интернете мало информации.

Заранее благодарю, и, если у Вас есть ссылка на электронный вариант книг, то укажите, пожалуйста.

[mod]Mathdream, предупреждение за дублирование тем![/mod]

[maxal]

По существу вопроса - выберите что-нибудь из этого. Например, лекции Носова.

[Mathdream]

Спасибо, но все что там есть про сведения - одно предложение. К тому же источник выглядит либо устаревшим - либо альтернативным - проблема остановки доказана через проблему самоприменимости.
А есть что-нибудь лучше? По каким книгам Вы это учили?

[Mathdream]

Честно говоря, складывается ощущение, что хороших книг по теоретической информатике на русском языке ВООБЩЕ НЕТ. Про английский не знаю - не искал.
Я уже не надеюсь на большой выбор литературы, где подробно объяснены вышеуказанные темы, но есть хоть что-нибудь стандартное и качественно структурированное????

[nworm]

Можете посмотреть

Катленд Н., Вычислимость. Введение в теорию рекурсивных функций

Роджерс Х., Теория рекурсивных функций и эффективная вычислимость

Там есть про сводимость по Тьюрингу