Каков абсолютный минимальный набор инструкций, необходимых для сборки полного процессора Тьюринга?

19

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

Предполагая, что языки программирования в основном являются абстракциями очень высокого уровня набора команд процессора, что является самым основным набором инструкций, необходимых для создания полной машины Тьюринга?

Примечание: я ничего не знаю о разнообразии аппаратных архитектур, но - для простоты - предположим, что это типичный процессор с ALU (при необходимости) и стеком инструкций. *

Эван Плейс
источник
Computer Science SE может быть лучшим местом для того, чтобы задавать подобные вопросы. (Нет смысла направлять вас туда сейчас.) Тем не менее, интересный вопрос.
Оскар Ског
По мере того, как количество инструкций, которые есть у ISA, уменьшается, так же как и значение КОЛИЧЕСТВА инструкций. МСА становятся более странными, когда у них меньше инструкций, чем у «оптимального» RISC. ISA только с одной инструкцией будет странно. // Они также становятся более странными, когда число увеличивается, а ISA становится CISC. // «странно», конечно, более или менее субъективно.
Оскар Ског

Ответы:

35

Оказывается, вам нужна только одна инструкция для построения машины, способной к вычислению Тьюринга. Этот класс машин, которые имеют только одну инструкцию и являются полными по Тьюрингу, называется One Instruction Set Computers или также в некоторой степени в шутку Ultimate RISC .

Йорг Миттаг
источник
4
+1 для получения наилучшего возможного ответа, если только не найдено решение с нулевой инструкцией (фактически, компьютеры с одной инструкцией иногда называют компьютерами с нулевой инструкцией, потому что в самой инструкции нет информации)
Cort Ammon - Восстановить Монику
4
Да, но эта одна инструкция не делает машину Тьюринга завершенной: магия находится во всех различных специализированных регистрах, к которым может обращаться инструкция. Я думаю, что ваш ответ указывает на то, что ОП приравнивает «компьютер» к «архитектуре фон Неймана», тогда как на самом деле категория «компьютеры» гораздо шире, чем эта.
Соломон Слоу
2
@jameslarge Волшебство не обязательно в специализированных регистрах. BitBitJump, SBNZ, SUBLEQ и SUBNEG вообще не нуждаются в регистрах, только в одной инструкции и немой памяти.
8bittree
2
@ 8bittree Хун! Наверное, я забыл, что проектирование странных, но полных по Тьюрингу архитектур - соревновательный вид спорта. Когда я прочитал ответ Йорга, я вспомнил своего друга из прошлого (около 1980-х), который планировал собрать «компьютер с одной инструкцией» из чипов серии 74LS, а затем запрограммировать его для эмуляции DecSystem 10. Я только что посмотрел на странице Википедии, и теперь я знаю, что его дизайн сегодня будет называться «Архитектура, запускаемая транспортом». Я не знаю, был ли он когда-либо доведен до конца.
Соломон Медленный
2
@jameslarge: Intel MMU также является полным по Тьюрингу (в частности, механизм ловушек). Это действительно очень странно, однако, это противоположность того, чтобы быть разработанным, это чистая случайность.
Йорг Миттаг
15

Есть много способов реализовать что-то, в чем можно реализовать машину Тьюринга.

Когда вы смотрите на процессоры, наиболее подходящим является, вероятно, модель регистрационной машины . Простейшим из них (с точки зрения символов) является двухсимвольный двухсимвольный символ ( markи blank). Если вы выбираете что-то не совсем эзотерическое, то inc(r), dec(r)и jz(r,z)(переход, если регистр rравен нулю для инструкции z) или clr(r)(сброс r) inc, je(i,j,z)(переход, если регистр i и j равны инструкции z).

Я видел упоминание о машине регистрации, которая:

  • inc (i, m) - увеличить регистр i и перейти к строке m
  • jzdec (i, m1, m2) - если регистр i равен 0, перейти к строке m, иначе уменьшить i и перейти к строке m2

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

Это оно. Ничего больше.


Так почему же не используются эти ультрарисковые процессоры? Это большая боль - написать для них компилятор, и вы отказываетесь от множества других вещей, которые может делать процессор. Это действительно приятно иметь побитовый and, addа не пытаться делать все с помощью увеличения регистров и циклов. Это основа любимого языка программирования под названием Brainfuck, который имеет 8 инструкций.

  • > увеличить указатель данных
  • < уменьшить указатель данных
  • + увеличивать данные в указателе данных
  • - уменьшить данные в указателе данных
  • . вывод данных на указатель данных
  • , читать ввод, сохраняя данные в указателе данных
  • [если данные в указателе равны нулю, вместо перемещения указателя инструкции вперед на один, переходите к команде после соответствующей ]команды
  • ]если данные в указателе отличны от нуля, вместо перемещения указателя инструкции вперед перейдите к команде после соответствующей ]команды

Можно найти компиляторы для Brainfuck, хотя делать в них даже простые вещи не очень интересно. Если вы не наслаждаетесь разочарованием, которое является целью языка.

Связанное чтение:

Сообщество
источник
5

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

  • Установите бит в текущем местоположении;
  • Сбросить бит в текущем местоположении;
  • Перейти к следующему адресу (увеличение регистра адресов данных);
  • Перейти к предыдущему адресу (уменьшить адресный регистр данных);
  • Проверьте бит в текущем местоположении данных.

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

9000
источник
5

Реализации

Этот ответ будет посвящен интересным реализациям процессоров, компиляторов и ассемблеров с одним набором команд.

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

Ciro Santilli 新疆 改造 中心 法轮功 六四 事件
источник
3

Какой абсолютный минимальный набор инструкций необходим для сборки полного процессора Тьюринга?

Йорг В. Миттаг сказал «один», но как насчет нуля?

Почему вы предполагаете, что «процессор» должен иметь «инструкции»?

Машина Тьюринга - это полный процесс Тьюринга, и он не работает с «инструкциями» как таковыми. У него есть правила , но правила не являются инструкциями, которые извлекаются из памяти с произвольным доступом.

Когда Алан Тьюринг придумал свою одноименную машину, он искал простейшую возможную модель «вычисления», чтобы он мог использовать математические методы, чтобы ответить на вопрос «Что вычислимо?»

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

FWIW, тип процессора, о котором вы думаете - тот, который извлекает инструкции из памяти, декодирует их и выполняет их, и который работает с данными, хранящимися в той же системе памяти, - известен как архитектура фон Неймана

https://en.wikipedia.org/wiki/Von_Neumann_architecture

Соломон Медленный
источник