lita_rk1_voprosy_i_otvety (803323)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Определения:• Машина Тьюринга определяется кортежем вида(). Здесь 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 ( ( )); проекцирующие функцииБазисные функции: нулевая (( ().)Правила: подстановка; рекурсия; минимизация..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)