lita_rk1_voprosy_i_otvety ([ЛиТА] Вопросы и ответы к РК1)

Определения:• Машина Тьюринга определяется кортежем вида(). Здесь Q – конечное множество состояний; V– конечный входной алфавит,– маркер начала ленты,– пустой символ (пробел);– символы направлениядвижения головки;– начальное состояние,– заключительное состояние; – функция переходов, являющаяся*+}{*+. Значение функции переходов, если оно определено, естьотображением вида, гдеконечное (возможно пустое) множество упорядоченных троек из соответствующего декартова произведения.• Конфигурация МТ – кортеж() где( )() {(((выводимости на множестве конфигураций –• Вычислимость по Тьюрингу – вербальная функцияпостроена МТ НАД алфавитом V такая, что .()()( ) . Отношение (непосредственной))))называется вычислимой по Тьюрингу, если может быть( )( )/ . ( )( )/; где применимость МТ к слову есть( ).• Нормальный алгорифм Маркова – Нормальный алгорифм А в алфавите V задаѐтся упорядоченной тройкой().Здесь S – упорядоченный набор формул подстановок в алфавите V (); P – набор, получаемый отметкой вS некоторых формул.

S – схема НА, P – заключительные формулы подстановки НА.• Процесс работы НА со словом – пусть слово. Процесс работы есть конечная\бесконечная последовательность слов()(), если, такая, что:определено в последовательности. Считается,чтоне определено в последовательности тогда и только тогда, когда(xn не поддаѐтсяалгоритму)• Вычислимость по Маркову – вербальная функцияпостроен НАназывается вычислимой по Маркову, если может бытьНАД алфавитом V такой, что (стрелкой а не справа, и это важно! Не путать с).и тем более с( )( )( )( )/ //– точка на самом деле под!1. Теорема композиции НА с доказательством.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Теорема: Каковы бы ни были НА А и В_в_ алфавите V, может быть построен НА С _над_ V так, что (). ( )( ( ))/Доказательство:̅*+, то ̅ *̅̅̅ ̅̅̅+1) Если.̅,2)3) Системаполучается из системы замыканием А согласно таблице:4) Система ̅ получается замыканием схемы В согласно таблице:I этап:II этап:III этап: ( )IV этап: ̅V этап: ̅ ̅VI этап:̅Следовательно, ( )( ( ))( )( )( )̅ ̅, где(̅̅̅̅̅̅( ) ( )( )( ))̅̅̅̅̅̅( )( )( )̅̅̅̅̅̅̅( )̅( )( ( ))( ( )).̅2.

Эквивалентность НА. Замыкание НА, естественное и формальное распространение НА на более широкийалфавит. Доказать эквивалентность НА и его замыкания.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Пусть есть два НАНАД алфавитом V. Они называются вполне эквивалентными, если( ( )( )) ( ( )( )), т.е.

( )( ) – определены или неопределены одновременно.,• Замыканием (схемы) НА А в алфавите V называется{, где{.,( ) дляДокажем, что А и его замыкание эквивалентны. Пусть ( ), значит( ) (естественный обрыв) илинекоторого z (на последнем шаге).( )( ).В ситуации естественного обрыва:( ).В ситуации последнего шага:( )и ( )( ). Если же( ), т.к. до командыТаким образом, если !А(х), то( ), то очевидно чтоочередь недойдѐт.• Естественным распространением [А в алфавите V] на более широкий алфавит(V’ содержащий V) называется НА[A’ в алфавите V’], где схема A’ совпадает со схемой А.Формальным распространением [А в алфавите V] на более широкий алфавитназывается НА [A’ в алфавите V’]{.3.

Понятие перевода в двухбуквенный алфавит. Формулировка теоремы о переводе.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~*+*+• Пусть дан алфавит. Определим операцию ,. Тогда для слова( )( ),, ( ) , ( ), причем ,.• Теорема: Каков бы ни был НАнад алфавитом V, может быть построен вполне эквивалентный ему(относительно алфавита V) НАв алфавите4. Определения изображения и записи НА. Примеры. Формулировка теоремы об универсальном НА.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~,, , , • Рассмотрим НА{в алфавите V.

Изображение этого НА есть,*+. Здесь, символ, а символ служит для разделения команд алгорифма.Пример: НА{. Его изображением будет*Рассмотрим алфавит.+ и изображение алгорифма А. Если пронумеровать каждый символ изсимвол из этого алфавита можно представить как*+, то k-й.

Записью алгорифма А называют его изображение, в которомкаждый символ представлен в данном виде. //криво, косо, со скрипом, но как-то так*+Пример:для ^ алгоритма, пронумеровав символы как, запись будет иметь вид 01110 010 011110 010 0111001111110 …• Теорема: Пусть V – произвольный алгорифм. Может быть построен алгорифм U над алфавитоми для любого НА А в V имеет место (⟦ ⟧ )( ) //на самом деле тут не эти скобочки, а «бабочка», .* + такой, что5. Теоремы объединения, разветвления, повторения НА (формулировки). Построение НА, распознающего равенствослов.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Теорема объединения: Каковы бы ни были НА А и В _в_ V, может быть построен НА С _над_ V такой, что ()( ( )( ) ( )).

//соединениеТеорема разветвления: Для любых НА А, В, С _в_ алфавите V может быть построен НА D _над_ V такой, что () ( ( )( )( )) и ( ( )( )( )).) ( )иТеорема повторения: Каковы бы ни были НА А,В _в_ V, может быть построен НА С _над_ V так, что (( ) тогда и только тогда, когда существует последовательность словопределено словотакая: если m=0, то̅̅̅̅̅̅̅̅̅̅̅) .(( )) ( ( )) ( ( ))/, тогдаy=x и ( )если же m>0, то (• Алгоритм распознавания равенства слов:(){алгоритм, Inv – инверсия,.({)( ( ).( )), где Id – тождественный6.

Определения разрешимого и перечислимого языка. Связь разрешимости и перечислимости. Примеры.. Доказатьневозможность разрешающего НА для языка, для которого невозможен полуразрешающий НА.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Рассмотрим алфавит V.Языкназывается алгорифмически разрешимым, если может быть построен НА_над_ алфавитом V такой, что:()( ( )( )). Алгорифм называют разрешающим алгорифмом; полуразрешающим алгорифмомназывают ̃ такой, что ̃ ( ).*+. Разрешающий его алгорифм может быть построен как, Пример разрешимого языка:, , где алгорифм С делит слово х пополам на слова х1 и х2, а EQ – сравнивает получившиеся половинки.Языкназывается алгорифмически перечислимым, если может быть построен НА_над_ алфавитомтакой,что для любого конструктивного натурального числа (//0 – КНЧ, если n – КНЧ, то n1 – тоже КНЧ) n имеет место применимость( )и ( ), а также для любого словаосуществимо КНЧ n такое, что ( ).Пример перечислимого языка: язык целых чисел.

Алгоритм: нумерация целых чисел в виде• Любое алгоритмически разрешимое множество алгоритмически перечислимо. Обратное не верно.• Теорема: Если для языканевозможен полуразрешающий НА, то невозможен и разрешающий.Доказательство: Предположим, что возможен разрешающий и при этом невозможен полуразрешающий НА. По теореме* . Следовательно, по построению,()( )разветвления, построим НА, те.–полуразрешающий НА. Противоречие.7.

Проблемы применимости и самоприменимости для НА. Доказательство неразрешимости проблемысамоприменимости.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Частная проблема применимости: «Можно ли построить НА А _над_ V так, что для фиксированного НА В _в_ V и( ))»произвольного словаимеет место: ( ) ( ( )Общая проблема применимости: «можно ли построить НА А _над_так, что для произвольного НА В _в_ V и(〈 〉 )( )»произвольного словаимеет место (〈 〉 )Проблема самоприменимости: «моэет ли быть построен НА А _над_так, что для произвольного НА В _в_ V имеет(〈 〉)(〈 〉)».место (〈 〉)(〈 〉)(〈 〉)• Лемма: невозможен НА А _в_ алфавитетакой, что для любого В _в_(〈〉)(〈〉)Теорема(1): Невозможен НА А _над_ V0 такой, что*+Доказательство: Пусть такой алгорифм А построен.

Тогда, по теореме о переводе, может быть построен)( ( )( )). Далее, рассмотримтакой, что (как естественное распространение А1 на V1. Тогда,( )( )*+(〈 〉)(〈 〉) – отсюда следует, что (〈 〉)(〈 〉)(〈 〉)(〈 〉) в алфавите*+ может быть построен НАТаким образом, для алфавитав алфавитетак, чтоимеет место(〈 〉)(〈 〉). Это невозможно, в силу леммы. Таким образом, каков бы ни был алфавит V, проблемасамоприменимости для НА _в_ алфавитеалгоритмически неразрешима.8.

Доказать алгоритмическую неразрешимость проблемы применимости для НА.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~*+ такой, что невозможен НА• Теорема(2): Пусть V – произвольный алфавит. Может быть построен НА В _в_( ).А _над_ , для которого для любого словаимело бы место ( )Доказательство: Определим алгоритм удвоения слова.По теореме об универсальном НА, построим НА U _над_ V2 так, что для( ).любых словаи НА D _в_ V2 имело место (〈 〉 ))( ( )()).Далее: построим НА_над_ V2 так, что (().Используя композицию,U1 построен _над_ V2.

Стало быть, U1 есть НА и _над_ V0, следовательно,по теореме о переводе, можно построить НА U2 _в_ V2 (т.е. в двухбуквенном)( ( )( )) Утверждается, что U2 естьрасширении V0) так, что (искомый НА В.Пусть теперь построен А, о котором говорится в условии теоремы. Тогда, для(〈 〉)(〈 〉)любого НА D _в_ V2, выполняется (〈 〉)(〈 〉)(〈 〉 〈 〉)(〈 〉) Таким образом, А может быть рассмотрен как НА _в_ М2 – имеем алгорифм,решающий проблему самоприменимости в том же алфавите.

Это невозможно, в силу теоремы(1) о неразрешимости проблемысамоприменимости.9. Понятие рекурсивной функции.~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~• Рекурсивной функцией называется функция вида. Множество рекурсивных функций содержитбазисные функции а также функции, образованные посредством определенных правил.( )); прибавление 1 ( ( )); проекцирующие функцииБазисные функции: нулевая (( ().)Правила: подстановка; рекурсия; минимизация..