|
Mathdream |
|
|
|
Здравствуйте. Посоветуйте, пожалуйста, книгу по теоринформатике, где подробно с доказательствами описывались бы основы - машины Тьюринга, классы сложности, теория вычислимости, проблема остановки, сведения по Левину, по Карпу, по Тьюрингу... По этим сведениЯм, кстати, даже в интернете мало информации.
Заранее благодарю, и, если у Вас есть ссылка на электронный вариант книг, то укажите, пожалуйста.
|
|
|
|
 |
|
Mathdream |
|
|
|
Здравствуйте. Посоветуйте, пожалуйста, книгу по теоринформатике, где подробно с доказательствами описывались бы основы - машины Тьюринга, классы сложности, теория вычислимости, проблема остановки, сведения по Левину, по Карпу, по Тьюрингу... По этим сведениЯм, кстати, даже в интернете мало информации.
Заранее благодарю, и, если у Вас есть ссылка на электронный вариант книг, то укажите, пожалуйста.
[mod]Mathdream, предупреждение за дублирование тем![/mod]
|
|
|
|
|
|
maxal |
|
|
По существу вопроса - выберите что-нибудь из этого. Например, лекции Носова.
|
|
|
|
|
|
Mathdream |
|
|
|
Спасибо, но все что там есть про сведения - одно предложение. К тому же источник выглядит либо устаревшим - либо альтернативным - проблема остановки доказана через проблему самоприменимости.
А есть что-нибудь лучше? По каким книгам Вы это учили?
|
|
|
|
|
|
Mathdream |
|
|
|
Честно говоря, складывается ощущение, что хороших книг по теоретической информатике на русском языке ВООБЩЕ НЕТ. Про английский не знаю - не искал.
Я уже не надеюсь на большой выбор литературы, где подробно объяснены вышеуказанные темы, но есть хоть что-нибудь стандартное и качественно структурированное????
|
|
|
|
|
|
nworm |
|
|
|
Можете посмотреть
Катленд Н., Вычислимость. Введение в теорию рекурсивных функций
Роджерс Х., Теория рекурсивных функций и эффективная вычислимость
Там есть про сводимость по Тьюрингу
|
|
|
|
|
