"Поиск всего кода в данном двоичном файле эквивалентен проблеме Остановки". В самом деле?
Просто читал высоко голосованный вопрос относительно Эмуляторов и заявления
Было доказано, что поиск всего кода в данном двоичном файле эквивалентен проблеме Halting.
Действительно торчал на меня.
Конечно, это не может быть правдой? Разве это не большой граф зависимостей?
Был бы очень признателен за дальнейшее понимание этого заявления.
4 ответа
Я полагаю, что имеется в виду "поиск всего кода, который когда-либо выполняется", то есть поиск покрытия, возможно, в сочетании с динамически генерируемым кодом. Это действительно может быть сведено к проблеме остановки.
Скажем, у вас есть идеальный инструмент покрытия, который найдет каждый фрагмент кода в программе, который когда-либо может быть выполнен (так что остальное - мертвый код). Учитывая программу Pэтот инструмент также сможет решить, будет ли расширенная программа (P ; halt) когда-либо выполняет halt инструкция, или ли halt часть мертвого кода. Таким образом, это решило бы проблему остановки, которая, как мы знаем, неразрешима.
Я не согласен с Ларсманом.
Проблема остановки говорит о том, что нет программы P существует, которая может взять любую программу и решить, выполняет ли эта программа halt инструкция. Позвольте мне процитировать Википедию:
Алан Тьюринг доказал в 1936 году, что общего алгоритма для решения проблемы остановки для всех возможных пар ввода программы не может быть. Мы говорим, что проблема остановки неразрешима на машинах Тьюринга.
С другой стороны, мы не пытаемся создать такую программу / алгоритм, но мы пытаемся найти весь код в этой / этих конкретных программах. Если мы перепроектируем программу и увидим, что она немедленно вызывает exit() (очень оптимистичный пример ситуации) мы доказали, что это вызовет haltа это было невозможно?!
Если мы пытаемся создать эмулятор, который может запускать любую программу, мы потерпим неудачу с тех пор, то вы можете (легко) свести это к проблеме остановки. Но обычно вы создаете эмулятор для чего-то вроде Game Boy, который поддерживает конечное количество игровых картриджей (программ) и, таким образом, это возможно.
Проблема остановки для конечных автоматов разрешима (хотя это может занять много жизней.....вселенной), и любая машина, которую вы можете эмулировать, является конечным автоматом. Просто запустите программу, и количество шагов ограничено числом возможных состояний; если это число превышено без остановки, то программа никогда не остановится, поскольку она должна быть в цикле.
Практически говоря, найти весь код - гораздо более простая проблема, если код не может использовать вычисляемые gotos. Вместо того, чтобы запускать код, вы просто берете все ветви ровно один раз в каждой возможной точке ветвления.
Я согласен с Ларсманом и считаю, что аргумент может быть уточнен. Во-первых, я должен согласиться с тем, что "поиск всего кода в заданном двоичном файле" означает в этом контексте наличие единственной вычислимой функции, которая определяет, какие байты во входном двоичном файле соответствуют выполняемым инструкциям.
РЕДАКТИРОВАТЬ: Если кто-то не ясно, почему здесь проблема, подумайте о запутанном машинном коде. Разборка такого кода является нетривиальной проблемой. Если вы начинаете разборку в середине многобайтовой инструкции, вы получаете неправильную разборку. Это нарушает не только указанную инструкцию, но обычно несколько инструкций за ее пределами. и т.д. посмотрите на это. (например, гугл "обфускация и разборка").
Эскиз стратегии, чтобы уточнить это:
Во-первых, определите теоретическую модель компьютера / машины, в которой программа закодирована в многоразрядных двоичных инструкциях, во многом аналогично машинному коду на "реальных" компьютерах, но сделана точной (и такой, чтобы она была завершена). Предположим, что двоичный код кодирует программу и все входные данные. Все это должно быть сделано точным, но предположим, что язык имеет (двоично-кодированную) инструкцию остановки, и что программа останавливается тогда и только тогда, когда она выполняет инструкцию остановки.
Во-первых, давайте предположим, что машина не может изменять программный код, но имеет память для работы. (предполагается бесконечным в интересных случаях).
Тогда любой заданный бит будет либо в начале инструкции, выполняемой во время выполнения программы, либо не будет. (например, это может быть в середине инструкции, или в данных, или в "мусорном коде" - то есть в коде, который никогда не будет выполняться. Обратите внимание, что я не утверждал, что они являются взаимоисключающими, как, например, инструкция перехода может иметь цель, которая находится в середине конкретной инструкции, тем самым создавая другую инструкцию, которая "при первом проходе" не выглядела как выполненная инструкция.).
Определите ins(i, j) как функцию, которая возвращает 1, если двоичный файл i имеет инструкцию, начинающуюся с позиции бита j, которая выполняется при запуске программы, кодированной i. Определите ins(i, j), чтобы быть 0 в противном случае. предположим, что ins(i, j) вычислимо.
Пусть halt_candidate(i) будет следующей программой:
for j = 1 to length(i)
if(i(j..j+len('halt')-1) == 'halt')
if(ins(i,j) == 1)
return 1
return 0
Так как мы запрещаем самоизменяющийся код выше, они могут остановить программу только для того, чтобы в некоторой позиции j выполнялась инструкция 'halt'. По замыслу halt_candidate(i) вычисляет функцию остановки.
Это дает очень грубый набросок одного направления доказательства. т.е. если мы предположим, что мы можем проверить, есть ли в программе i инструкция в местоположении j для всех j, то мы можем закодировать функцию остановки.
Для другого направления необходимо закодировать эмулятор формальной машины внутри формальной машины. Затем создайте программу плюс входы i и j, которая эмулирует программу i, и когда инструкция в битовой позиции j выполняется, она возвращает 1 и останавливается. Когда выполняется любая другая инструкция, она продолжает выполняться, и если симуляция когда-либо имитирует функцию "остановки" в i, эмулятор переходит в бесконечный цикл. Тогда ins(i, j) эквивалентен halt(emulator(i,j)), и поэтому проблема остановки подразумевает проблему поиска кода.
Конечно, нужно предположить, что теоретический компьютер для этого является эквивалентом нерешаемой проблемы остановки. В противном случае для "настоящего" компьютера проблема остановки решаема, но неразрешима.
Для системы, которая допускает самоизменяющийся код, аргумент является более сложным, но я ожидаю, что не так уж и отличается.
РЕДАКТИРОВАТЬ: Я считаю, что доказательством в случае самоизменения было бы реализовать эмулятор кода системы плюс самоизменения в статический код плюс система данных выше. Затем остановка с использованием самоизменяющегося кода, разрешенного для программы i с данными x, аналогична остановке в вышеупомянутой статической системе плюс система данных с двоичным файлом, содержащим эмулятор i и x в качестве кода плюс данные.