Минимальный набор команд для решения любой проблемы с компьютерной программой

Ответ 1

Нет необходимости. Минимальный теоретический компьютер требует только одной инструкции. Они называются One Instruction Set Computers (OISC для краткости, вроде как RISC).

Существует два типа. Первая - теоретически "чистая" одна машина, в которой инструкция действительно работает как обычная инструкция в обычных ЦП. Обычно команда:

subtract and branch if less than zero

или их вариаций. В статье wikipedia приведены примеры того, как эту единую инструкцию можно использовать для написания кода, который эмулирует другие инструкции.

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

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

Ответ 2

Это является следствием Turing Completness, что было установлено много десятилетий назад.

Алан Тьюринг, известный ученый-компьютер, доказал, что любая вычислимая функция может быть вычислена с помощью Turing Machine. Машина Тьюринга - очень простое теоретическое устройство, которое может выполнять только несколько вещей. Он может считывать и записывать на ленту (т.е. память), поддерживать внутреннее состояние, которое изменяется содержимым, считываемым из памяти, и использовать внутреннее состояние и последнюю ячейку памяти для чтения, чтобы определить, в каком направлении перемещать ленту, прежде чем читать следующую ячейка памяти.

Операции присваивания, условности и цикла достаточны для имитации машины Тьюринга. Чтение и запись памяти и сохранение состояния требует назначения. Изменение направления ленты на основе состояния и содержимого памяти требует условностей и циклов. "Циклы" на самом деле немного более высокого уровня, чем того, что на самом деле требуется. Все, что действительно необходимо, - это то, что поток программы может каким-то образом отскочить назад. Это означает, что вы можете создавать циклы, если хотите, но язык не должен иметь явную конструкцию цикла.

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

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

Ответ 3

Минимальное множество - это одна команда, но вам нужно выбрать подходящую, например - Один компьютер с набором инструкций

Когда я изучал, мы использовали такой "компьютер" для вычисления факториала, используя только одну инструкцию:

SBN - Subtract and Branch if Negative:
SBN A, B, C

Значение:

if((Memory[A] -= Memory[B]) < 0) goto C  
// (Wikipedia has a slightly different definition)

Ответ 4

Известные реализации одного набора команд (OSIC)

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

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:

• https://github.com/hasithvm/subleq-verilog Verilog, Xilinx ISE.
• https://github.com/purisc-group/purisc Verilog и VHDL, Altera. Может быть, у этого проекта есть бэкэнд Clang, но я не могу его использовать: https://github.com/purisc-group/purisc/issues/5
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp С++ - ассемблер и эмулятор на основе.

Смотрите также

• Какой минимальный набор инструкций необходим для того, чтобы любой язык ассемблера считался полезным?
• https://softwareengineering.stackexchange.com/questions/230538/what-is-the-absolute-minimum-set-of-instructions-required-to-build-a-turing-comp/325501

Ответ 5

В 1964 году Бом и Якопини опубликовали документ в котором они продемонстрировали, что все программы могут быть написаны только с тремя структурами управления: структура последовательности, структура выбора и структура повторения.

Ответ 6

Программисты, использующие Haskell, могут утверждать, что вам нужны только Contional и Loop, потому что назначения и изменчивое состояние не существуют в Haskell.