Обсуждение:Примеры неразрешимых задач: проблема соответствий Поста

Материал из Викиконспекты
Перейти к: навигация, поиск
англоязычные термины
англоязычные источники, в частности, википедия
Выполним m-сведение множества пар из машины Тьюринга (МТ) и строки w , где M(w) не зависает — у этого множества есть название
"Договоримся, что состояния в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?
"можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо
побольше интервики
форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.
Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.
пока все, но мне кажется, до хорошо читаемой статьи еще надо что-нибудь переписать

--Дмитрий Герасимов 12:15, 9 декабря 2012 (GST)