Минимальный набор системы команд

Навеяно обсуждением на форуме Zen-ского языка Forth "Минимальный набор слов Форта": http://fforum.winglion.ru/viewtopic.php?t=100. А каков интересно минимальный (подчеркиваю - минимальный, а не просто более-менее удобный) набор команд команд для, скажем, Intel-овского процессора. Что-то, понятно, абсолютно необходимо, а что-то можно смоделировать. Вопрос, конечно, чисто теоретический, поскольку глупо было бы не воспользоваться тем, что есть. Его можно переформулировать так: что составляет абсолютно достаточный (базовый) набор команд, что необходимо всегда, а что - полезным, но не обязательным придатком ?

 

mov
add
jmp
or/and/not
shl/shr
mul/div

ИМХО всё.

 

А разве mul/div не эмулируются сложением в цикле ?

 

в принципе можно поизвращаться, но это долго. Хотя по сабжу можно и без них.

 

Если идти по пути однокомандного процессора, то по идее должно хватить:
sub
jc
jmp

если нужен доступ к сегментным регистрам то тогда еще добавится mov
если нужен доступ к внешним устройствам, то тогда добавится еще in/out, но вообще можно было отобразить их регистры на память.
ну а для обработки прерываний придётся еще добавить iret.

 

shl/shr, mul/div - можно заменить комбинацией из нескольких not и add.
A or B = not (not A and not B) => or тоже не нужен
Поэтому мой вариант: mov,add,jc,and,not.

 

на самом деле ответ прост - 1 (одна) команда. В подтверждение - http://www.wasm.ru/forum/viewtopic.php?id=8642

 

вобще в самом деле нафига нам больше? у нас же нет ограничений на методы адресации, поэтому всё что нам нужно сможем построить из xor'а, sub'а или add'а 8)

 

Минимальный, говорите? xor

 

Минимальный, говорите?
A xor B = (not(A) and B ) or (not(B) and A)
конечно и ADD, и SUB можно реализовать через AND, NOT, OR
JMP Label можно сделать через ADD IP,(offset Label - $)
IF b THEN A ELSE B через (A and b) or (not(b) and B)
наверное минимальный набор MOV, NOT, (AND/OR)

 

Mikl__
a xor b = not(not(a) or b) or not(a or not(b))

 

по теореме Моргана not(a or b)=(not a) and (not b) поэтому можно и так, и так,
а вообще, по мотивам алгебры логики и Крис Касперски "ПРИМЕРЫ РЕАЛЬНЫХ ВЗЛОМОВ. КАК ВЗЛОМАТЬ Emulated Solar CPU" любая операция сводится к Стрелке Пирса или к штриху Шеффера
A 0 0 1 1
B 0 1 0 1
PIRS 1 0 0 0 Стрелка Пирса (ИЛИ-НЕ)
SHEFF 1 1 1 0 Штрих Шеффера (И-НЕ)

NOT A == PIRS A, A
MOV A, B == PIRS (PIRS B, B)
OR A, B == PIRS (PIRS A, B)
AND A, B == PIRS (PIRS A, A), (PIRS B, B)
XOR A, B == AND (OR A, B), NOT(AND A,B)
A ? B : C == OR (AND A, B), NOT(OR A, (NOT C)))
JMP A == MOV [EIP],A
а к минимальному набору необходимо добавить загрузку в/из память

 

Mikl__
Любая логическая операция сводится к стрелке Пирса. А вот как с ее помощью проэмулировать сложение? Ну хотя бы инкремент? Без него комп будет не совсем полноценным...

 

Atlantic
Побитовое сложение сведем к логическим операциям
CARRY0 =A0 and B0
C0 = A0 xor B0
C1 = CARRY0 xor A1 xor B1
CARRY1 = (not C1) or (CARRY0 and A1 and B1)
....

 

Был неправ, ступил Но такой код придется писать для определенной разрядности операндов. А цикл - не сделать, так как для него нужен инкремент, который мы сейчас и делаем

 

Машина Тьюринга как раз и реализует минимальную систему команд. Google->Wikipedia

Ее можно реализовать на операциях НЕ+И (или НЕ+ИЛИ), обратной связи и суперпозиции

 

Atlantic
Инкремент/декремент можно получать табличным преобразованием,
не все циклы строятся на счетчиках, некоторые продолжаются пока выполняется/не выполняется определенное условие

 

Там AFAIK 5 команд - двигать ленту вправо/влево, стоп, считать значение с ленты, изменить значение на ленте. Можно обойтись и 3мя = PIRS, mov, hlt

 

Есть еще машины Шё(о)нфилда там вообще три команды inc,dec, jz =)))

 

А где можно почитать об этих самых машинах Шёнфилда ? Я знаю, что есть хорошая книга по матлогике написанная Шёнфилдом; это он самый ? Но в этой книге никакой информации о "машине" я не сыскал