# конспект · шаг 7 из 7
Конспект: машина Тьюринга, универсальная машина и разрешимость
Понятия
Машина Тьюринга - конечная таблица, бесконечная лента и головка, которая ходит в обе стороны, читает и перезаписывает по одной клетке. Конфигурация - состояние, лента и положение головки.
Три исхода: принять, отвергнуть, не остановиться.
Моделирование - машина одной модели, дающая на каждом входе тот же исход, что машина другой. Тезис Чёрча-Тьюринга - всё вычислимое по чёткой процедуре вычислимо на машине Тьюринга.
Универсальная машина - получает описание машины ⟨M⟩ и вход w, делает то же, что M на w.
Разрешимый язык - есть машина, которая на каждом входе останавливается с верным ответом. Распознаваемый - есть машина, которая принимает его строки, а на остальных вправе не остановиться.
Что унести
ШАГ: ( состояние, символ под головкой )
→ ( что записать, L или R, новое состояние )
нет строки в таблице - отвергнуть;
на левом краю сдвиг влево оставляет головку на месте
исписано всегда конечное число клеток: бесконечен запас, а не память
прибавить 1, младший разряд слева: 1 → 0, вправо, дальше;
0 или пусто → 1, принять
1101 (11) → 0011 (12) за 3 шага
aⁿbⁿcⁿ вычёркиванием, 5 состояний, 17 строк:
a → X, первая b → Y, первая c → Z, назад к X
n 2 4 8 16 32
шагов 23 77 281 1073 4193 n проходов по 3n клеток: ~n²
«не остановилась» - не «отвергла»:
машина, идущая вправо по пустым клеткам, ответа не даст
ВАРИАНТЫ - языки те же, цена разная
несколько лент t шагов → порядка t² на одной
лента в обе стороны того же порядка
память с адресами многочлен
недетерминизм порядка bᵗ: 100 шагов угадывания
→ 10³⁰ конфигураций
один стек - КС-языки; два стека - машина Тьюринга
(левый стек слева от головки, правый справа)
та же таблица на двух стеках: 23, 77, 281, 1073, 4193 шага - шаг в шаг
тезис Чёрча-Тьюринга: не теорема; опровергнуть можно, доказать нельзя
что вычислимо - не зависит от модели;
за сколько - зависит, но в пределах многочлена
УНИВЕРСАЛЬНАЯ МАШИНА
описание машины - строка: "000R0 011R1 100R1 110R0 0__R+"
29 символов, 87 бит
одна программа выполняет любое описание;
описание можно подать на вход машине, в том числе ей самой
все машины выстраиваются в список: строки по длине,
одной длины - по алфавиту
распознаёт L: на строках из L принимает;
на остальных отвергает ИЛИ не останавливается
разрешает L: останавливается всегда;
принимает строки из L, отвергает остальные
язык и дополнение распознаваемы → язык разрешим
(две машины по шагу по очереди)
предел шагов не делает решателя:
предел 6 7 27 97 871
20 8 16 не знаю не знаю не знаю
120 8 16 111 118 не знаю
200 8 16 111 118 178
ЧТО РАЗРЕШИМО
вопрос ДКА КС-грамматика машина Тьюринга
принимает ли строку да да, CYK нет
пуст ли язык да, обход да, пометка нет
равны ли два языка да, пары нет нет
равенство ДКА: обход пар состояний в ширину;
плохая пара - принимает ровно один
p и q состояний - не больше p · q пар
путь до плохой пары - кратчайшая различающая строка
один испорченный переход в автомате на 6 состояний
→ строка 10111
пустота грамматики: помечать порождающие нетерминалы,
пока пометки появляются
Ловушки джокера
Принял «не остановилась» за «нет». Отвергнуть - значит остановиться.
Решил, что вторая лента добавит возможностей. Она добавляет скорости, не больше квадрата.
Сослался на тезис как на теорему. Доказаны равносильности моделей; тезис - обобщение.
Счёл данные и программу разными вещами. Строка, которую выполнят, - программа, откуда бы она ни пришла.
Заменил «не знаю» на «нет» по тайм-ауту. Ошибка случится ровно на тех входах, ради которых проверку запускали.
Проверил равенство автоматов тестами. Испорченный автомат может совпадать с правильным на всех коротких строках.
Перенёс приём с автоматов на грамматики или программы. Равенство грамматик неразрешимо; для программ неразрешимо почти всё.
Взял тьюринг-полный язык там, где хватило бы слабого. Вместе с силой приходит невозможность проверить программу до запуска.
Проверь себя
Чем машина Тьюринга отличается от автомата со стеком и что из этого следует? Почему дополнительные ленты и угадывание не меняют класс языков и сколько они стоят? Что такое универсальная машина и почему из неё следует, что программа может получить на вход саму себя? Чем разрешающая машина отличается от распознающей? Почему равенство двух конечных автоматов можно проверить, хотя строк бесконечно много?
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий