Может ли каждый самоизменяющийся алгоритм моделироваться несамодифицирующимся алгоритмом?

Если у нас есть какая-либо произвольная компьютерная программа, которая может изменить ее инструкции, возможно ли смоделировать эту программу с помощью программы, которая не может изменить ее инструкции?

Редактировать:

Я новичок в stackexchange, поэтому не уверен, что мне разрешено задавать НОВЫЙ вопрос здесь, но здесь идет речь: Хорошо, поэтому доказательство того, что это возможно, на самом деле очень просто, как вы, ребята, показали. Теперь я задаюсь вопросом: существуют ли проблемы, для которых более эффективно (и в какой степени) использовать наиболее эффективный самоизменяющийся алгоритм для решения проблемы по сравнению с наиболее эффективным алгоритмом несамодифицирующегося ввода-вывода, эквивалентным эквивалентному?

computability computation-models turing-completeness church-turing-thesis user56834
источник

Ответы:

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

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

Дэвид Ричерби
источник

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

Александр - Восстановить Монику

@AlexanderMomchliov существуют процессоры, которые могут изменять части своего набора команд на лету (но да, идея та же самая - программируемая часть - это данные, микроконтроллер, который запускает ее, является интерпретатором - хотя и указывает на микроконтроллер внутри ячейки ПЛИС может быть хитрым)

Джон Дворак

в ответ на это: «у вас вполне может быть универсальная машина Тьюринга, которая позволяет моделируемой модели изменять свое собственное описание». Я думаю: разве это не задает вопрос? потому что теперь вам все еще нужно доказать, что моделируемая ТМ может фактически моделировать алгоритм самоизменения, верно? Вполне возможно, что существует самоизменяющаяся программа, которая сама по себе НЕ является машиной Тьюринга, поэтому мы не можем использовать полноту Тьюринга, чтобы показать, что она может быть смоделирована, поскольку полнота Тьюринга относится к моделированию ТМ и самоизменяющейся модели. Альго не ТМ.

user56834

@ Programmer2134 Это вообще не задает вопрос. Какой бы процессор вы ни думали, на котором вы запускаете свою программу самоизменения, я могу смоделировать этот процессор на машине Тьюринга. Чтобы объяснить это по-другому, исходная программа представляет собой конечную последовательность инструкций, некоторые из которых изменяют саму программу. Каждая из команд может быть смоделирована UTM, каждая из модификаций может быть смоделирована, и каждая из измененных команд может быть смоделирована. На любом этапе этого процесса нет ничего, что выходило бы за рамки возможностей машин Тьюринга.

Дэвид Ричерби

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

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

Это, конечно, экзистенциальный аргумент: есть это эквивалентная программа. Но мы также знаем, что существуют рекурсивные (то есть вычислимые) компиляторы между любыми двумя Turing-Complete языками, поэтому вы получаете программу той формы (читай: на языке), которую вы хотите.

Рафаэль
источник

Чтобы добавить ответ Дэвида Ричерби :

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

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

Александр - Восстановить Монику
источник

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

Корт Аммон

@CortAmmon: Если мы рассматриваем «жизнь» как алгоритм, каковы его входные и выходные данные? Как можно доказать, что любой эквивалентный алгоритм (имеется в виду, любой алгоритм, который выдает тот же результат, если дан один и тот же вход), должен быть самоизменяющимся?

Руах

@ruakh Если бы я утверждал, что жизнь была самоизменяющимся алгоритмом, входные данные были бы сами собой, а его выходные были бы сами собой. Доказать, что он не может быть сведен к немодифицируемому алгоритму, было бы хитрее, но я думаю, что это популярная гипотеза. В конце концов, сколько людей хотят верить, что они могут быть сведены к алгоритму, который может работать на компьютере?

Корт Аммон

@CortAmmon: я не могу быть сведен к алгоритму, работающему на компьютере, потому что этот алгоритм больше не "я"; Я больше, чем мои входы и выходы. Но если мы будем исходить из предположения , что я буду просто алгоритм, то лавируя на « который может работать на компьютере» не меняет ничего. Re: «Если бы я утверждал, что жизнь была самоизменяющимся алгоритмом, входные данные были бы сами по себе, а его выходные были бы сами собой»: в этом случае я думаю, что вы будете сильно отклоняться от CS и опасно близки к крэкпоттерам.

Руах

@CortAmmon Программа, которая выводит себя сама, в качестве ввода просто cat. (Не каламбур, хотя кошки и являются живыми существами)

user253751