Я согласен с Ларсманом и считаю, что аргумент может быть уточнен.Во-первых, я должен согласиться с тем, что «поиск всего кода в заданном двоичном файле» в этом контексте означает наличие единственной вычислимой функции, которая определяет, какие байты во входном двоичном файле соответствуют выполняемым инструкциям.
РЕДАКТИРОВАТЬ: Если кому-то не ясно, почему здесь возникает проблема, подумайте о запутанном машинном коде.Разборка такого кода является нетривиальной проблемой.Если вы начинаете разборку в середине многобайтовой инструкции, вы получаете неправильную разборку.Это нарушает не только указанную инструкцию, но обычно несколько инструкций за ее пределами.и т.д. посмотрите на это.(например, Google «обфускация и разборка»).
Эскиз стратегии, чтобы уточнить это:
Сначала определите теоретическую модель компьютера / машины, в которой программа кодируется в несколькобитовые бинарные инструкции, очень похожие на машинный код на «настоящих» компьютерах, но они сделаны точными (и такими, что они завершаются).Предположим, что двоичный код кодирует программу и все входные данные.Все это должно быть сделано точным, но предположим, что язык имеет (двоично-кодированную) инструкцию остановки, и что программа останавливается тогда и только тогда, когда она выполняет команду остановки.
Сначала давайте предположим, чтомашина не может изменить программный код, но имеет память для работы.(предполагается бесконечным в интересных случаях).
Тогда любой данный бит будет либо в начале инструкции, выполняемой во время выполнения программы, либо не будет.(например, это может быть в середине инструкции, или в данных, или в «мусорном коде», то есть коде, который никогда не будет выполняться. Обратите внимание, что я не утверждал, что они являются взаимоисключающими, как, например, инструкция переходаможет иметь цель, которая находится в середине конкретной инструкции, тем самым создавая другую инструкцию, которая «при первом проходе» не выглядела как выполненная инструкция.).
Определите 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 в качестве кода плюс данные.