Теорема Коэна
и проблема Halting Problem Алана Тьюринга.
Май 2001, Sassa для ZF#5
О чем это?
Der Steine im Sumpf
Macht keine Ringe
(нем.: камень в болоте
не вызывает волнения)
В данной статье рассматривается знаменитая теорема Коэна (Fred
Cohen; Кохен) о невозможности существования совершенного антивируса:
программы, которая сможет _безошибочно_ определять, заражена ли
программа каким-то вирусом вообще или нет. Тут мы отсылаем недоверчивых
к трудам самого Коэна, [1], в частности к части Detection of Viruses:
там он сразу и говорит об этой проблеме. Также отправим читателя и к
статье Дэвида Чесса (D.M.Chess) [2], антивирусного исследователя из
IBM, который продолжает обсуждать теорему Коэна (и тоже приходит к
выводам, что это невозможно; он находит еще ряд ограничений, но мы их
касаться не станем).
Взглянув одним глазом на саму теорему, мы плавно перейдем к
проблеме Halting Problem Алана Тьюринга (A.M.Turing), краткое описание
труда коего мы разместили для любопытных в Приложении А, "Машина
Тьюринга". Тем, кто знаком с этим теоретическим вычислительным
устройством, мы рекомендуем не тратить время, а сразу продолжить
прочтение статьи; разве только читатель предпочитает удостовериться в
правильности наших предпосылок в этой сфере или желает помочь нам
отыскать еще пару грамматических ошибок.
Обратим внимание, что поскольку решение теорем одинаково, то решив
Halting Problem, мы тем самым находим решение теоремы Коэна (а именно
отысканием подходов к осуществлению (все-таки!) мечты юзера мы и
займемся).
Данная статья не находит формального описания алгоритма
универсального детектора вирусов. Она также не доказывает его
возможность. Она лишь опровергает доказательство теоремы Коэна, а
заодно и Halting Problem. Заметим, что могут существовать и другие,
пока не сформулированные, теоремы, которые все-таки могут доказать
существование неразрешимых проблем на пути программистов.
Тьма
...там Бес-просветный мрак,
и человеку бедному так худо,
что даже Я щажу его; покуда.
И.В.Гете, "Фауст"
(а Вы думали "Дом глав Дюны"? J
Ранним утром, когда вирусы только стали вылупливаться из своих
коконов, глаза людям открыл Коэн. И они увидели тьму и бепросветность:
он стал говорить им, что нельзя придумать супер-защиту от вирусов.
Потому что для супер-защиты нужен алгоритм, который бы со 100%
достоверностью первого рода отличал семя от плевел: мы же не хотим
защищаться от "хороших" программ; и мы хотим защищаться от всех-всех
вирусов.
Фактически, антивирус может быть представлен в виде программы AV
таким образом [2]:
AV: if A(p) then heal, else exit.
Эта запись настолько понятна, что лишь для формальности объясним,
что она означает. Итак, программа AV - это такая программа, которая
вызывает некую функцию классификации на некоторой другой программе p,
которую мы и тестируем на зараженность. Если функция классификации A()
возвращает, скажем, true, то это значит, что программа p заражена (и
поэтому ее нужно вылечить). Если же функция A() возвращает что-то
другое, то это значит, что программа p чистая и можно ничего не делать.
Собственно, алгоритм heal может быть предельно прост: выдать
предупреждение; или, может, удалить зловредную программу p.
Итак, если подумать, то, в сущности, любой антивирус можно
абстрагировать до именно такого кода.
Ключевой момент антивируса - алгоритм A(p), который классифицирует
программы на зараженные и остальные.
Коэн, если коротко, стал утверждать, что нельзя построить такой
универсальный классификатор A(p), который бы мог ловить все вирусы,
даже на данный момент не существующие, и при этом не трогал других
программ. Аргументом была следующая программа P [2] (или [1], но там не
так коротко):
P: if A(P) then exit, else spread.
То есть, программа вызывает классификатор на _самой_себе_, и делает
ровно противоположное! Таким образом, поскольку антивирус AV использует
точно тот же алгоритм, то его действия будут некорректны: если A(p) по
каким-то причинам классифицирует программу как зараженную, то антивирус
попробует ее вылечить, в то время как на самом деле программа P просто
завершается (всегда! поскольку функция A(p) вызывается с константой,
P), и потому вирусом не является. Наоборот, если функция A(p) выдаст
вердикт, что эта программа P не является зараженной, то антивирус AV ее
проигнорирует; в то время как на самом деле она станет размножаться!
Внимательный читатель, несомненно, согласится, что принципиально
вопрос состоит не в том, что A(p) не способен отличить этот особый
случай - "недоразумение", "парадокс", - а в том, что этот алгоритм не
может _дать_правильный_ответ_! Для этого ему нужно знать, кто его
вызвал, чтобы корректировать свое поведение в соответствии с ситуацией
и давать consistent ответы. Возможно, если кто-то из читателей и не
заметил этого сразу, то наверняка сейчас у него уже есть парочка
решений этого вопроса. Для полноты статьи мы изложим и свои взгляды на
решение этого, казалось бы, тупика. Но для начала мы укажем на еще
одну, весьма типичную, теорему; практически близнецы!
Теорема Коэна находится на расстоянии вытянутой руки от теоремы
Halting Problem Тьюринга. Это отмечает, например, Чесс в частной беседе
с автором. Собственно, это и подтолкнуло автора на мысль о совокуплении
проблем в одну.
Суть проблемы Halting Problem (извините, мне не известно русское
произношение этого термина; но из сути Вам сейчас все станет ясно) вот
в чем. Итак, мы умеем составлять программы для Машины Тьюринга (МТ; не
путать с тяжелыми мотоциклами J. Теперь хорошо бы узнать, можно ли ее
запускать. Скажем, что, если эта программа никогда не завершится? Что,
если она войдет в бесконечный цикл по какой-то причине (ну, ошибка в
программе!)? Неплохо бы выяснить это до ее запуска. Причем, это можно
узнать _только_ до запуска. Поскольку пока программа работает, мы не
можем сказать, когда же она завершится. И завершится ли она вообще.
Вдруг как только мы решим, что она повисла, она тут же выходит из
тупика? Таким образом, только проанализировав код можно сказать,
конечна ли она. Суть излагаемой проблемы желающие могут проверить по
книге Алана Тьюринга "О вычисляемых числах", сосканированные страницы
которой были доступны автору в Интернете [3] (о-о!.. теперь они уже и
распознали эти страницы?!).
Однакоже, человеку свойственно ошибаться (потому, собственно, мы и
хотим знать, а не повиснет ли программа), поэтому мы не можем доверить
вопрос проверки кода человеку: так мы можем бесконечно близко
приближаться к совершенной программе, но никогда нельзя быть уверенным,
что проверено все "до единого гвоздя". Так Тьюринг возжелал поручить
эту задачу самой МТ: она ведь безошибочно точна; пусть скажет точно,
конечна ли программа. Но буквально "через два абзаца" он говорит, что
такая программа вообще не возможна. Поскольку возможно существование
такой программы P, которая будет делать совершенно противоположные
дейтсвия:
P: if H(P) then not_dead_which_eternal_lies, else exit.
То есть, если некоторый алгоритм классификации возвращает true
(скажем, у Тьюринга речь шла о просто двух ответах) для конечных
программ, и возвращает именно это значение для этой программы, то
программа переходит в вечный цикл. Зачем? Just for the heck of it! Зато
если H(p) возвращает что-то другое, что означает, что программа
бесконечна, то программа просто завершается. Так, нельзя написать
программу HD, которая на основании H(p) будет говорить, конечна ли
заданная программа, с достоверностью 100%. Удрученному пользователю
якобы ничего не остается, как проверять свой код вручную.
И вот мы и станем рассматривать пути опровержения этого
доказательства. Мы попытаемся отыскать такие черты у современных
процессоров, которые требуют усоврешенствования понятия МТ. После этого
мы станем утверждать, что доказательство более не верно, предложим пути
опровержения его, а вдобавок подстелим немного философической соломки
(если придется падать #-) в подкрепление верности наших умозаключений о
необходимости усовершенствования МТ.
Забрезжил свет
...А Ильич-то голый!
Б.Гримм, Голый король J
Прочь шутки и хохмы. Отложим это до поры. Решением вселенских
вопросов займемся-ка лучше.
Решение 1.
Первое, что вскочило в голову - наличие многозадачности. Озарение
принесло автору первое решение: в ОС UNIX есть такая замечательная
функция - fork(). Примечательно в ней то, что она создает копию
нынешнего процесса с разницей в одном-единственном бите: возвращаемый
функцией результат. После выполнения этой функции имеем два идентичных
процесса - два автомата - продолжающие выполнение именно с точки
возврата из функции. При этом родительский процесс получит PID
порожденного процесса - ненулевое значение, - а порожденный процесс
получит ноль как результат выполнения функции. Если процессы не
обрабатывают возвращаемое значение, то они становятся идентичными.
if (fork()){
//... это место выполняется только родительским процессом
}else{
//... это место выполняется только порожденным процессом
}
Листинг 1. Пример кода с различием процессов
fork();
// ... это место выполняется обоими процессами
Листинг 2. Пример кода с одинаковыми процессами; автоматы идентичны
Итак, в точке алгоритма H(p), где он определяет, что программа p -
"недоразумение", нужно создать копию автомата, и сделать так, чтобы
один автомат вернул True, а другой - False. Тогда противоречивая
программа P расщепится на две, одна из которых тут же завершится, а
другая - перейдет в вечный цикл. Классификатор тоже раздвоится в своем
мнении. Но поскольку одно из его мнений будет "программа P повиснет",
то можно документировать "двойственный" ответ как утвердительный ответ,
и достоверность распознания не уменьшится.
Конечно, мы исходили из предположения, что программа P не сможет
обнаружить и общаться с другими ее копиями (хотя это и возможно в той
же ОС UNIX). Мы не станем касаться этого вопроса по той причине, что
H(p) очень даже запросто может эмулировать протокол общения, и вынудить
нужную копию программы P пойти по заданной ветке, если она
противоречивая (то есть, в принципе _может_ пойти по любой из веток, но
нужно специфическое условие). Вопрос эмуляции протокола - это другая
тема. Главное, что логическая проблема "как дать правильный ответ
лжецу" (обращаем внимание читателя и на эту фразу; мы к ней еще
вернемся) решена.
Заключение из решения 1.
Наш ответ - "и да, и нет"!
Решение 2.
Вместо fork() можно вызвать exit(). И таким образом проблема решена
снова. Программа P, которая раньше считалась недоразумением,
автоматически становится конечной. Классификатор должен теперь выдать
сообщение "программа P конечна" (презумпция невиновности J, запустить
классификатор, и _если_ (заметьте, будьте так добры, и эту
знаменательную точку нашего решения) будет получен ответ True, то
выдать "ой, оказывается, программа P бесконечна!".
Заключение 1 из решения 2.
Как мило: просто не станем отвечать тем, кто может оболгать нас J
Заключение 2 из решения 2.
На практике же могут возникнуть вопросы, связанные с вызовом
exit(). Поскольку это API, его возможно (?) перехватить (ну, в
DOS-Windows - точно; в UNIX - зависимо от привилегий). А _если_
возможно перехватить, то возможно и исказить реальный исход событий в
программе P. Так что, займемся теперь теорией неуловимого останова.
Модификация МТ
Рассмотрим предлагаемые нами коррективы, которые нужно внести в
Машину Тьюринга. Узрите же в них и нынешние реализации процессоров!
Поскольку суть МТ в том, что существует конечное число состояний, и
для каждого из них определены правила перехода (_программа_), то может
существовать такая таблица переходов, что в ней все строки будут
заняты, кроме одной, определенной самой программой как состояние
останова, и поэтому не известное функции H(p) заранее (на этапе ее
разработки). Поэтому встает несколько задач: разрешить H(p)
модифицировать таблицу переходов, научиться модифицировать ее таким
образом, чтобы и произвольная программа P, и наш детектор HD,
останавливались правильно. Мы выдвигаем такие требования к МТ:
0. программа должна уметь конвертировать состояние в данные
(преобразование состояния в само имя; архитектура x86:
дизассемблирование кода с возможностью его последующего анализа)
1. программа должна уметь конвертировать данные в состояние
(преобразование имени состояния в само состояние; архитектура x86:
расчет точки перехода; генерация новой инструкции)
2. пространство имен состояний МТ должно быть не ограничено (в
теоретическом случае; мы к этому еще вернемся; архитектура x86: даже с
1МБ памяти существуют способы адресации всех 4ГБ, хотя и получим
исключение; максимальная длина инструкции - 16 байт, а корректных
инструкций отнюдь не 2^128)
3. МТ должна теперь останавливаться не только в случае, когда она
переходит в состояние с неопределенными для данного символа переходами,
но и в случае, если встречается переход в несуществующее состояние (сие
добавлено в связи с возражениями Дэвида Чесса при переписке; автору это
казалось очевидным следствием из определения МТ, но мы не возражаем
добавить его сюда) (обработка ошибочных ситуаций в связи с наличием
Свойства 2; архитектура iAPX386: исключения при попытках обращаться к
физически несуществующей памяти; исполнение неопределенной инструкции -
скажите, ведь как легко соорудить искомый автомат на базе этой
архитектуры; нужно всего лишь останавливаться вместо вызова обработчика
исключения!)
Свойство 0 предоставляет механизм анализа программ. Кажется, оно и
так существует в МТ, но мы его все равно добавим в этот список,
поскольку оно связано с остальными.
Свойство 1 (в неразрывной связи со Свойством 0) позволяет
модифицировать поведение классификатора в критических случаях.
Свойство 2 позволяет программе сгенерировать нужное, даже не
существующее, состояние: предоставляет в пользование неуловимый
останов.
Свойство 3 делает останов неуловимым. Заметим, что в данной машине
МТ можно говорить о наличии нормального останова и останова по причине
"не-программа". Так, противоречивая программа P становится
"не-программой". Сам классификатор, правда, тоже, но мы знаем, что это
означает, и считаем все равно запуск именно этой "не-программы"
полезным занятием. Теперь мы можем даже сначала написать на ленте "НЕ
ПРОГРАММА", а если классификатор что-то вернет, то в зависимости от
ответа заменить на "ВИСНЕТ" или "НЕ ВИСНЕТ". Суть остается той же, что
и раньше: мы можем отличить заведомо бесконечные программы от
остальных. В рамках решения Halting Problem, таким образом, такое
разделение остановов МТ не существенно, и мы его дальше рассматривать
не будем.
Итак, теперь возможно существование такого алгоритма H(p), который
при обнаружении противоречия в тестируемой программе P расчитывает
некое новое состояние, которого нет в P, и совершает переход туда. МТ
останавливается и программа P конечна. Теперь возможно существование
такой программы-детектора HD, которая оставляет неопределенными все
состояния, которые может вычислить H(p) (ведь алгоритм генерации нового
состояния известен). Таким образом при тестировании программой HD
некоей программы P HD будет способна получить классификацию от функции
H(p) и не будет препятствовать корректному останову даже в
парадоксальных случаях.
Поскольку во всем остальном МТ осталась точно такой же, то с
помощью этой МТ можно проверять программы для любой реализации МТ. То
есть, достаточно существование одной такой МТ, которую я согласен
оставить у себя, если Вы усматриваете пороки в коммерческом
использовании такого автомата, который может просто остановиться, без
окошка с кнопочкой OK. J
Решение оставшихся вопросов
Свойство 2 требует неограниченного пространства состояний. В общем-
то, поскольку таблица состояний хранится в памяти из физических
материалов, то это не возможно, ведь материала во Вселенной весьма
ограниченное в этом плане количество. Однако, во-первых, можно говорить
о _достаточно_ большом количестве памяти; а именно - на место для
одного состояния больше, чем нужно тестируемой программе P, а это
всегда возможно. Это можно задокументировать в свойствах
программы-детектора HD, как требование к памяти. ...А кстати, ведь
поскольку в самой программе P присутствует вызов функции H(p), то ей
ведь _тоже_ нужно столько памяти J
...А во-вторых, в рамках решения проблемы останова необходимо лишь
уметь правильно реагировать на такие состояния: остутствие строки в
таблице состояний всегда можно зафиксировать за конечное время (таблица
конечна) и интерпретировать ее (отсутствующую строку) как пустую, то
есть, как останов.
Интересно, что некоторые считают, что существует проблема детекции
самого парадоксального случая, ведь якобы нужно уметь ловить _все_
реализации H(p) (ведь речь идет об _алгоритме_, а не программе). Лично
мне кажется такое утверждение безусловно необоснованным. Исходя из сути
проблемы детекции, алгоритм H(p) просто не в состоянии _дать_правильный
_ответ_. Так, достаточно всего лишь проверять, присутствует ли в
тестируемой программе P копия "меня", копия именно той реализации H(p),
которая проводит классификацию. Это сделать ну просто элементарно:
побайтное сравнение! В случае, если "меня" там нет, то можно не бояться
давать какой бы то ни было ответ: H(p) запущена не из тестируемой
программы P, а потому даже если и окажется парадоксальной для другой
реализации H(p), то это проблема той реализации. "Мне" можно отвечать
что угодно: поскольку "та" реализация ведь что-то все же вернет, то я
могу узнать, что именно, и выдать ответ, соответствующий _действиям_ P,
который, впрочем, может и расходиться с ответом "той" реализации H(p).
Ведь "я" никак не могу отвечать за чужие ошибки.
Надеемся, мы ясно выразились.
О необходимости такой функции автомата: программно-неуловимый
останов.
...А почему, собственно, ее не должно быть? Почему мы доверяем коду
перехватывать буквально все? Ведь в этом кроется ошибка назначения
доверия: вызывающий код - "заинтересованное лицо"! Ну, подумайте сами:
программист знаком со спецификацией функции, и ему известны допустимые
параметры. Значит, он может и сам проверить их допустимость. А если же
вызов происходит все же с недопустимыми параметрами, и функция
сигнализирует об этом, то почему мы считаем, что это "нечаянно", и
почему мы доверяем проверку этого сигнала самому вызывающему коду? Код,
передавший недопустимые параметры, некорректен; как же он может принять
корректное решение в спорном случае (принять объективное решение при
рассмотрении жалобы нижестоящих по отношению к вышестоящему - Нему)?!
Да-да, именно в этом и проблема неразвешиваемых синих экранов: при
нажатии Ctrl-Alt-Del порою Windows не перезагружается, а снова попадает
в это состояние, без каких-либо визуальных (и такое ощущение, что и
внутренних) отличий. А все оттого, что допускает ошибки и решает их
один и тот же код.
Мы, таким образом, предлагаем новую (новую?) концепцию
защищенности. Мы предлагаем на аппаратном уровне (поскольку мы верим
только аппаратуре) ввести иерархию доверия обработки исключительных
ситуаций, на самой вершине которой находится сам процессор (считая, что
уж он-то работает без ошибок J. Процессор решает вопрос единственным
образом: останавливается. Потому что это единственное, что он может
делать действительно безопасно. Любители маркетинга могут сильно не
возмущаться, что де, пользователю не нужен компьютер, который может
остановиться. Потому что разве лучше, если он просто зацикливается? 8-)
А вдобавок заметим, что ведь такой процессор нужен только разработчикам
ПО, чтобы проверять свои программы на "весучесть".
Если позволите, еще немного демагогии.
Возвращаясь к философии проблемы "как ответить лжецу". Нужно
вопросить его "а как _ты_ считаешь?" и уметь сказать расплывчатое "ну,
вот видишь!", вместо "да" или "нет". Корректная программа (HD) сделает
презумпцию невиновности, и ответ останется "not guilty" до тех пор пока
функция H(p) не опровергнет этого. Лжец (точнее, оболгатель) презумпции
не делает, что функция H(p) и должна заметить. Молчание - лучший ответ,
господа. J И в этом философия нашего последнего решения. В первом
случае - в случае с честной программой - ответственность тогда ложится
на плечи того, кто делает презумпцию, а во втором случае
ответственность ни на кого не ложится, поскольку никто ничего не
говорил. Философически, предлагаемая функция H(p) более не отвечает на
вопрос "эта программа виснет?", а пытается опровергать утверждение "эта
программа не виснет". В чем и безопасность. Решение принимает босс;
поскольку H(p) - не босс, она лишь предоставляет факты; или не
предоставляет никаких фактов. МТ, Вселенский судия, _должна_
предоставить механизм избежания наказания за молчание; должна
обеспечить каналом правосудия и правопорядка. Оболгать можно только
какой-то ответ. Молчание оболгать нельзя. И наказать за нежелание
отвечать тоже нельзя. Это второй ключевой момент философии нашего
решения.
Отметим, что в решении-1, в решении с двойным ответом, по сути мы
отдаем "боссу" два отчета. В надежде, что он не станет искать такого же
ответа среди уже имеющихся. В таком случае, в случае, где программа
беззащитна и обязана дать хоть какой-то ответ, остается только уповать,
что мы сможем сказать "я ж говорил!" прежде, чем босс заметит
противоречие.
Do you trust, what I trust? Me, myself, and I!..
* * *
Приложение А. Машина Тьюринга
Это приложение является необязательным для изучения. Его идея -
всего лишь изложить суть Машины Тьюринга. Для тех, кто с ней знаком,
здесь вряд ли найдется что-то интересного. Но мы ни в коем случае Вас
не отгоняем J
Приложенная в списке использованных источников книга написана в
довольно академическом стиле [4], а впридачу еще и на английском,
поэтому изложим как можно более просто определение машины Тьюринга и ее
применимость; для начинающих.
Машина Тьюринга - это теоретическое устройство, которое может
исполнять разные программы для обработки произвольного ввода (если
хотите более строго - ввод не произвольный, а пользовательский J.
Естественно, результаты работы выдаются пользователю. Эта машина не
знает, как работать с клавиатурой или с экраном. Потому что она
теоретическая. Ее применение, в общем-то, не в области расчетов, а в
области доказательства их возможности.
Устройство ввода-вывода Машины - оперативная головка, которая
способна читать и записывать ячейки конечной или бесконечной ленты,
обрабатывая каждую из них по одной. Тьюринг предлагает использовать
всего два вида символов: 0 и 1. Только 1 несет информацию; числа он
предлагает записывать в виде последовательности единиц на одну больше,
чем само число. Так число ноль будет представлено в виде одной единицы;
число один - в виде последовательности из двух единиц; число два - три
единицы подряд, и т.п. Таким образом, он предлагает универсальную
машину для расчетов.
Машина читает с помощью головки символ из ячейки, в зависимости от
считанного символа всегда записывает что-либо в текущую ячейку как
определено программой, перемещает головку на одну позицию "влево" или
"вправо". После этого машина переключается в новое состояние (снова же,
как определено программой) и цикл повторяется:
1. чтение (ввод!)
2. принятие решения
3. запись (вывод!), последующее смещение головки (потоковость ввода
и вывода) и переход в новое состояние (изменение процедуры принятия
решения)
Машина останавливается, если считан такой символ, для которого в
программе не описано процедуры принятия решения (либо машина бесконечно
продолжает писать 0, если переводить книгу точно), и программа
считается выполненной. После выполнения программы лента содержит
результат.
Программа для такой машины выглядит как таблица состояний. Каждая
строка соответствует состоянию, а колонки - считанному символу. Так,
если считан символ 0, то Машина принимает решение, взятое из одной
колонки; если 1 - то из другой колонки. Клеточка таблицы содержит имя
нового состояния, символ, который нужно записать и направление смещения
головки. Если клетка пустая - это значит, что если Машина считает
символ, соответствующий ей, то она остановится (см. "не описано
процедуры принятия решения"). Можно подумать, что это встретилась
внештатная ситуация, а можно так и не думать.
Думается, из этого уже многое ясно. Пример программы, складывающей
два числа, настолько известен, что мы его приводить не станем. Приведем
-ка программу, занимающуюся умножением: складывает число само с собой
столько раз, сколько задает второе число.
Задание: все числа положительные. Они представлены в виде
последовательности единиц на одну длиннее, чем само число. На
бесконечной ленте два числа, разделенных одним нулем. Головка стоит на
две клетки левее, чем первый сомножитель. В результате выполнения
программы на ленте должно оставаться только одно число, и оно должно
означать результат умножения.
Пример: 5 х 4 = 20
до - ...001111110111110000...
^головка
после - ...01111111111111111111110...
Результирующая позиция головки не важна.
Решение.
Инициализируем результат в 0.
Станем вытирать по одной единичке справа у второго множителя, и для
каждой вытертой единички будем выполнять внутренний цикл: добавление к
результату числа, равного первому множителю. Алгоритм, предлагаемый в
том самом известном алгоритме сложения, не годится:
Ответ:
Вот таблица для МТ. Для каждого состояния задано две клетки. Первая
цифра - что записать. Буква - куда сдвинуть головку: L(eft) или
R(ight). Второе число - номер следующего состояния.
Состояние 0 1
0 1R1 - ; начальное состояние
1 0R1 1R2
2 0R3 1R2
3 0L4 1R3
4 0L6 0L5
5 0L6 1L7
6 - 0L6 ; конечное состояние
7 0L8 1L7
8 - 1L9 ; в этом месте не может быть 0
9 0R2 0L10
10 0L11 1L10
11 1R12 1L11
12 0R13 1R12
13 1L9 1R13
В Интернете есть страничка, на которой можно задать программу для
Машины Тьюринга и начальное состояние ленты (правда, конечной) [5], и
получить результаты вычислений. Для той реализации МТ эту программу
необходимо немного модернизировать, поскольку та МТ не умеет работать с
бесконечными лентами.
Источники
(Все линки 22 Мая 2001 были живыми)
1. Fred Cohen, Computer Viruses: Theory and Experiments //
http://all.net/books/virus/
(существует также копия в Computers & Security, Volume 6 (1987), 22
-35.)
2. David M. Chess and Steve R. White. An Undetectable Computer
Virus. // IBM Thomas J. Watson Research Center, Hawthorne, New York,
USA. http://www.research.ibm.com/antivirus/SciPapers/VB2000DC.htm
3. A.M.Turing. On Computable Numbers, With an Application to the
Entscheidungsproblem. // http://www.abelard.org/turpap2/tp2-ie.asp
|
