07052001 (1109970)

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

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

7 мая 2001 г.

Определение. вычисляет – не всюду определенную функцию –, если для любого набора если определена, то , работая над кодом набора , останавливается и выдает результат – код , а если не определена, то неприменима к коду .

Пример. Машина, которая топчется на месте, вычисляет нигде не определенную функцию.

Рассмотрим алфавит и символ . Построим машину , удваивающую слова, помещая между ними « »: , .

Где - некоторые символы, не принадлежащие алфавиту .

Удобно, чтобы слова состояли из непустых букв ( ). Занумеруем буквы, состояния и сдвиги следующим образом: . Команды тоже можем кодировать: как в алфавите .

Составим слово – код машины.

Закодировав все команды машины в одну последовательность – декодируемую, поскольку мы знаем, что код каждой команды содержит ровно 5 слов из одних 1,– можно будет попытаться применить любую машину, в алфавите которой содержатся * и 1, к этому коду. Если таким образом заставить машины работать над собственными кодами, некоторые из них будут останавливаться, а некоторые нет. Первые называются самоприменимыми, вторые – несамоприменимыми. Возникает проблема решения самоприменимости, а именно, построения машины , которая по коду машины определяла бы, самоприменима ли эта машина или нет. Вскоре будет доказано, что ЭТО НЕВОЗМОЖНО.

Пусть существует такая машина , что .

Утверждение. Если существует машина , решающая проблему самоприменимости, то существует машина со свойствами, что (1) применима к кодам несамоприменимых машин и (2) неприменима к кодам самоприменимых машин.

Доказательство. Очень короткое. Пусть – конечное состояние , – новое (не употребленное пока) значение состояния, которое мы провозгласим конечным для . Применим сначала ко входному коду, а затем одну из двух команд: или . (Иными словами, припишем к системе команд машины эти две команды – и это будет система команд машины ).

Утверждение. Не существует машины со свойствами (1), (2).

Доказательство. Если самоприменима, то она, по (2), несамоприменима. Если несамоприменима, то она, по (1), самоприменима. Противоречие.

Теперь возьмем какую-нибудь машину и какую-нибудь информацию и зададимся вопросом, применима ли к , а точнее, о существовании машины, решающей эту проблему. Для этого составим код машины и припишем к нему код данной информации: .

Утверждение. Не существует машины, решающей проблему применимости.

Доказательство. Допустим, что существует такая машина . Тогда машина решает проблему самоприменимости: , (определяет применимость к ).

Пусть у нас есть машина . Она как-то переводит слова друг в друга, например, . Назовем два слова эквивалентными относительно , если они этой машиной переводятся друг в друга. Проблема установления эквивалентности слов для любых двух, поданных на вход, алгоритмически неразрешима (не существует алгоритма, решающего ее). В этой связи в заключение приведем теорему Райса. Напомним, что свойство называется нетривиальным, если существует объект, обладающий этим свойством, и существует объект, не обладающий этим свойством.

Теорема. Задача узнавания, обладает ли любой объект нетривиальным свойством или нет, АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМА.

Доказательства этого утверждения в нашем курсе не будет.

.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций