Нахождение всего кода в заданном двоичном файле эквивалентно проблеме остановки. Действительно?

Я считаю, что имеется в виду «поиск всего кода, который когда-либо выполнялся», то есть поиск покрытия, возможно, в сочетании с динамически сгенерированным кодом. Это действительно можно свести к проблеме остановки.

Скажем, у вас есть идеальный инструмент покрытия, который найдет каждый фрагмент кода в программе, который может когда-либо быть выполнен (так что остальное - мертвый код). При наличии программы P этот инструмент также сможет решить, будет ли расширенная программа (P ; halt) когда-либо выполнять инструкцию halt или часть halt является мертвым кодом. Таким образом, это решит проблему остановки, которая, как мы знаем, неразрешима.

Я не согласен с ларсманом.

Проблема остановки говорит о том, что не существует P программы, которая могла бы взять любую программу и решить, выполняет ли эта программа инструкцию halt. Позвольте процитировать википедию:

Алан Тьюринг доказал в 1936 году, что не может существовать общий алгоритм для решения проблемы остановки для всех возможных пар программа-ввод. Мы говорим, что проблема остановки неразрешима для машин Тьюринга.

С другой стороны, мы не пытаемся создать такую ​​программу / алгоритм, но мы пытаемся найти весь код в этой / этих конкретных программах. Если мы перепроектируем программу и увидим, что она немедленно вызывает exit() (очень оптимистичный пример ситуации), мы доказали, что она вызовет halt, хотя это было невозможно ?!

Если мы пытаемся создать эмулятор, который может запускать любую программу, мы потерпим неудачу, поскольку тогда вы можете (легко) свести это к проблеме остановки. Но обычно вы создаете эмулятор для чего-то вроде Game Boy, который поддерживает ограниченное количество игровых картриджей (программ), и поэтому это возможно.

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

С практической точки зрения найти весь код намного проще, если код не может использовать вычисляемые переходы. Вместо того, чтобы запускать код, вы просто берете все ветки ровно один раз в каждой возможной точке ветвления.

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

РЕДАКТИРОВАТЬ: если кто-то не понимает, почему здесь проблема, подумайте о запутанном машинном коде. Дизассемблирование такого кода - нетривиальная задача. Если вы начнете разборку в середине многобайтовой инструкции, вы получите неправильную разборку. Это нарушает не только данную инструкцию, но, как правило, несколько других инструкций. и т. д. посмотрите в это. (например, погуглите "обфускация и разборка").

Набросок стратегии, чтобы сделать это точным:

Во-первых, определите теоретическую модель компьютера / машины, в которой программа закодирована в многобитовых двоичных инструкциях, очень похожих на машинный код на «реальных» компьютерах, но сделана точной (и такой, что она завершена по Тьюрингу). Предположим, что двоичный код кодирует программу и весь ввод. Все это должно быть сделано точно, но предположим, что в языке есть (в двоичном коде) команда остановки, и что программа останавливается тогда и только тогда, когда она выполняет команду остановки.

Во-первых, предположим, что машина не может изменять программный код, но имеет память для работы. (в интересных случаях предполагается бесконечным).

Тогда любой заданный бит будет либо в начале инструкции, которая выполняется во время выполнения программы, либо не будет. (например, он может быть в середине инструкции, или в данных, или в «мусорном коде» - то есть код, который никогда не будет запущен. Обратите внимание, что я не утверждал, что они являются взаимоисключающими, как, например, инструкция перехода может иметь цель, которая находится в середине конкретной инструкции, тем самым создавая другую инструкцию, которая «на первом проходе» не выглядела как выполненная инструкция.).

Определите 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_candidate (i) вычисляет функцию остановки.

Это дает очень грубый набросок одного направления доказательства. т.е. если мы предполагаем, что можем проверить, есть ли в программе i инструкция в позиции j для всех j, то мы можем закодировать функцию остановки.

В другом направлении нужно закодировать эмулятор формальной машины внутри формальной машины. Затем создайте программу плюс входы i и j, которая имитирует программу i, и когда выполняется инструкция с битовой позицией j, она возвращает 1 и останавливается. Когда выполняется любая другая инструкция, она продолжает выполняться, и если симуляция когда-либо имитирует функцию «остановки» в i, эмулятор переходит в бесконечный цикл. Тогда ins (i, j) эквивалентен halt (emulator (i, j)), и поэтому проблема остановки подразумевает проблему поиска кода.

Конечно, нужно предположить, что теоретический компьютер эквивалентен известной неразрешимой проблеме остановки. В противном случае для «настоящего» компьютера проблема остановки разрешима, но неразрешима.

Для системы, допускающей самомодифицирующийся код, аргумент более сложен, но я не ожидаю, что он будет отличаться.

РЕДАКТИРОВАТЬ: Я считаю, что доказательством самомодифицирующегося случая будет реализация эмулятора кода системы плюс самомодифицирующийся в статическом коде плюс система данных выше. Затем остановка с помощью самомодифицирующегося кода, разрешенного для программы i с данными x, такая же, как остановка в системе статический код плюс данные выше с двоичным файлом, содержащим эмулятор, i и x как код плюс данные.