Вопрос 23. Тезис Поста. Теорема о распознавании и порождении языков, заданных произвольными грамматиками.
ТЕЗИС ПОСТА : грамматика типа 0 может быть представлена как МТ .
Ассоциативное исчисление – формальная система которая эквивалентна грамматике без нетерминальных знаков и продукции которых действуют в обе стороны .
Полусистемной ТУЭ – одностороннее ассоциативное исчисление , когда правило имеет вид a->b .
Теорема 1 : (о непротиворечивости арифметик )
Теорема 2 ( о неполноте арифметике натуральных чисел) существует выражение в арифметике натуральных чисел которое невозможно ни опровергнуть ни доказать.
Теорема 3 (неполноценность арифметик ) – означает , что если утверждение которое невозможно ни доказать ни опровергнуть использовать в качестве аксиомы формальной системы то все равно арифметика будет неполной .
В свете изложенного легко может быть докозана теорема о неразрешимости языков порождаемыми произвольнаыми грамматиками . Действительно если для произвольной грамматике может быть построена МТ представляющая этот язык (порождающая или распознающая ) то по внешнему продукций никакое свойство этого языка не является алгоритмически разрешимым в соответсвии с теоремой Райса .
Теорема 31 : (о представимости формальных систем МТ ) Для любой МТ распознающей некоторый формальный язык существует МТ порождающая этот язык и наоборот .
ДКВ: Пусть задан МТ расопзнающая язык L МТ=< V,Q,P> Tp(a)={И/Л}
2) построим МТ порождающюю этот язык следующим образом МТп перебирает всевозожные строки начиная с некоторой строки a в лексографическом порядке , и каждый раз запускает МТр которая вычисляет предикат с восстановлением . Если предикат равен истине то знак и удаляется и машина остается с записью на месте некоторой строки b (которая является следующей строкой исходного языка ) Впротивном случае порождается следующая строка и процесс повторяется.
Если больше нет строк начиная с некоторой строки a машина не остановится , что означает правильную вычислимость функции Тп . Так как формальный язык как правило счетен то за конечное мы не сможем наблюдать зацикливание машины , сможем наблюдать выполнимость .
3) Докажем обратную теорему : пусть задана МТп порождающая строки некоторого языка в лесикографическом порядке , где a начальная строка возможно не принадлежащая , b следующая строка принадлежащая языку .
4) построим МТр – следующим образом : изменим последний знак в строке a в направлении обратном лексикографическому порядку . А затем запустим МТп работающую на правой полу ленте предварительно скопировав исходную строку Тп(а !! а’) – а‘ строка на единицу меньше а . Если Тп остановится и результат ее работы будет строка тождественная а , то перед а записывается значение предиката и , иначе л.
Тр(?)=(И, если ?=Tп(?’) или Л, если ??Тп(?’))
Вторая часть теоремы о существовании распознающей МТ справедлива для счетнах языков
Замечание : если мы потребуем вычисления усеченного предиката , когда распознающая машина останавливается когда строка принадлежит языку и не останавливается в противном случае , то теорема справедлива для конечных языков .

Вопрос 24. Детерминированная и недетерминированная машина Тьюринга.
Детерминированность : Пусть МТ=<V,Q,P> qia0->qi’ ai’dk P э Q*A*! Q*A*D
Продукции Р задаются на множестве Q,A,D
P: Q*A->Q*A*D для всех (q,a)Э Q*A существует (q,a,d) Э Q*A*D
Если отображение р функция то такой автомат называется , если отображение р нефункционально то МТ – недетерминированна и будет существовать ситуация когда возможно принятие двух и более резличных команд в некотором состоянии МТ . Единственный метод реализации недетерминированных автоматов является метод размножения (комбинаторная сложность реализации ), которая заключается в следующем
Пусть имеется МТ=<V,Q,P> Предположим , что МТ недетерминирована т.е. существует как минимум две строки имеющие различные правые части qi ai -> qi’ ai’ dk и qi ai ->qi’’ ai’’ dk’
Назовем группу таких команд слоем . Максимальное число слоев М=!Q!*!V!
Если в некотором состоянии возможен альтернативный выбор m команд (принадлежащих одному слою )
То размножаем исходную МТ в числе экземпляров равным m . Это множество конечно.