У меня есть общее представление о том, как процессор обрабатывает инструкции, но я трачу свое время на работу в основном на языках высокого уровня. Может быть, кто-то, кто работает ближе к железу, может дать ценную информацию.
Предполагая, что языки программирования в основном являются абстракциями очень высокого уровня набора команд процессора, что является самым основным набором инструкций, необходимых для создания полной машины Тьюринга?
Примечание: я ничего не знаю о разнообразии аппаратных архитектур, но - для простоты - предположим, что это типичный процессор с ALU (при необходимости) и стеком инструкций. *
hardware
low-level
turing-completeness
Эван Плейс
источник
источник
Ответы:
Оказывается, вам нужна только одна инструкция для построения машины, способной к вычислению Тьюринга. Этот класс машин, которые имеют только одну инструкцию и являются полными по Тьюрингу, называется One Instruction Set Computers или также в некоторой степени в шутку Ultimate RISC .
источник
Есть много способов реализовать что-то, в чем можно реализовать машину Тьюринга.
Когда вы смотрите на процессоры, наиболее подходящим является, вероятно, модель регистрационной машины . Простейшим из них (с точки зрения символов) является двухсимвольный двухсимвольный символ (
mark
иblank
). Если вы выбираете что-то не совсем эзотерическое, тоinc(r)
,dec(r)
иjz(r,z)
(переход, если регистрr
равен нулю для инструкцииz
) илиclr(r)
(сбросr
)inc
,je(i,j,z)
(переход, если регистр i и j равны инструкции z).Я видел упоминание о машине регистрации, которая:
который также завершен по Тьюрингу - это машина регистра Минского, хотя у него есть другие ограничения на данные на ленте (это должен быть номер Геделя, хранящий состояние, а не отдельные регистры)
Это оно. Ничего больше.
Так почему же не используются эти ультрарисковые процессоры? Это большая боль - написать для них компилятор, и вы отказываетесь от множества других вещей, которые может делать процессор. Это действительно приятно иметь побитовый
and
,add
а не пытаться делать все с помощью увеличения регистров и циклов. Это основа любимого языка программирования под названием Brainfuck, который имеет 8 инструкций.>
увеличить указатель данных<
уменьшить указатель данных+
увеличивать данные в указателе данных-
уменьшить данные в указателе данных.
вывод данных на указатель данных,
читать ввод, сохраняя данные в указателе данных[
если данные в указателе равны нулю, вместо перемещения указателя инструкции вперед на один, переходите к команде после соответствующей]
команды]
если данные в указателе отличны от нуля, вместо перемещения указателя инструкции вперед перейдите к команде после соответствующей]
командыМожно найти компиляторы для Brainfuck, хотя делать в них даже простые вещи не очень интересно. Если вы не наслаждаетесь разочарованием, которое является целью языка.
Связанное чтение:
источник
Я подозреваю, что машина Post - это самая простая форма устройства, полного по Тьюрингу. Вам нужен запас памяти с битовой адресацией, адресный регистр, который указывает на текущее местоположение данных, и пять инструкций:
Я не думаю, что легко изобрести что-то намного более простое с аппаратной точки зрения, хотя, возможно, существует что-то еще более ограниченное.
источник
Реализации
Этот ответ будет посвящен интересным реализациям процессоров, компиляторов и ассемблеров с одним набором команд.
movfuscator
https://github.com/xoreaxeaxeax/movfuscator
Компилирует код C, используя только
mov
инструкции x86, показывая очень конкретным образом, что достаточно одной инструкции.Полнота Тьюринга, кажется, была доказана в статье: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
subleq
https://esolangs.org/wiki/Subleq :
Смотрите также
/programming/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869
источник
Йорг В. Миттаг сказал «один», но как насчет нуля?
Почему вы предполагаете, что «процессор» должен иметь «инструкции»?
Машина Тьюринга - это полный процесс Тьюринга, и он не работает с «инструкциями» как таковыми. У него есть правила , но правила не являются инструкциями, которые извлекаются из памяти с произвольным доступом.
Когда Алан Тьюринг придумал свою одноименную машину, он искал простейшую возможную модель «вычисления», чтобы он мог использовать математические методы, чтобы ответить на вопрос «Что вычислимо?»
Вам будет трудно спроектировать эквивалентную по Тьюрингу машину, которая будет проще, чем настоящая машина Тьюринга.
FWIW, тип процессора, о котором вы думаете - тот, который извлекает инструкции из памяти, декодирует их и выполняет их, и который работает с данными, хранящимися в той же системе памяти, - известен как архитектура фон Неймана
https://en.wikipedia.org/wiki/Von_Neumann_architecture
источник