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

fplab
Ну у нас в университете был курс теория алгоритмов я о машине Шёнфилда услышал там. Могу пошустрить конспект лекций. Если надо еще...

 

nobodyzzz
Интересно как XOR или MOV организовать через INC/DEC?

 

Если несложно, пошустрите, пожалуйста

 

вобщето в алгебра логики любая ЛФ может быть представлена в базисе И-ИЛИ-НЕ, при чем И и ИЛИ взаимозаменяемы. по крайней мере нас так учили. на этих элементах строили и суматоры, рассматреволе схему умножения деления. по этому сколнен согласится с Mikl__ насчет mov/or/not

 

Atlantic

Сложение через логические операции и сдвиг: пусть мы складываем X=1011b Y=1110b
+1011 = X X + Y = (X xor Y) + 2(X & Y) на каждом шаге будем получать частичную сумму
1110 = Y и переносы из предыдущих разрядов, до тех пор пока либо частичная сумма,
0101 = X xor Y частичная сумма либо переносы не станут равными нулю, причем если
10100 = 2(X&Y) переносы слагаемые равны, получаем сдвиг влево на первом шаге
10001
001000
11001
0000000
0011001

 

ага. и если не ошибаюсь на той же схеме можно получить вычитание в допкодах.

 

FreeManCPM
Не ошибаешься

 

Mikl__

Плюс справа - это, я так понимаю, XOR? В итоге, обошлись стрелкой Пирса и сдвигом влево на 1 бит - 2 операции.

 

Atlantic
Плюс справа - это арифметический плюс, подробности смотрите внимательно в #25 количество операций для сложения, в конечном итоге, (так же как и для умножения) зависит от вида слагаемых (сомножителей) Минимальный набор: стрелка Пирса, mov, shl/shr, jcc

 

Mikl__
А, вот теперь врубился - это было тождество записано. Применяя его последовательно, можно свести второе слагаемое к нулю, и тогда первое будет равно искомой сумме.

 

Atlantic
IMHO операции INC/DEC внутри АЛУ организованы схемотехнически в виде двоичных счетчиков, а не на основе сложения/вычитания с 1
Для любителей "прятать" операции:
X xor Y = (X or Y)-(X and Y)
X and Y = (X or Y)-(X xor Y)
X + Y = (X or Y)+(X and Y)

 

В универе был курс "Теория программирования" на котором доказали, что система опреаций
mov [переменная],0
mov [переменная1],[переменная2]
inc [переменная]
cmp [переменная1],[переменная2]
jz/jnz
Является полной, то есть с её помощью можно реализовать любой вычислительный алгоритм для натуральных чисел.
А если зафиксировать рамер переменной, то можно реализовывать алгоритмы для целых чисел.

 

вот собсно пошустрил. соре за задержку=))
http://ifolder.ru/2246727

 

Благодарствую !!! Непременно посмотрю

 

После перерыва, вызванного тяжким внедрением очередного проекта, появилось, наконец, время почитать о машинах Шенфилда. Все показалось странно знакомым, все это когда-то встречалось. Поясню.
Открываю книгу Марвина Минского "Вычисления и автоматы" в которой весьма подробно, с примерами и картинками описана машина практически в точности совпадающая с описанием машины Шенфилда. Правда, о самом Шенфилде - почему-то ни слова
Ладно, думаю, поищу дальше - может корифей забыл о Шенфилде или переводчики "постарались" (что, кстати, вряд ли - в те времена книги по математике переводили профессионалы, да и редакторскую работу выполняли минимум КФМ, а часто и доктора).
Открываю книгу Дж.Булоса и Р.Джеффри "Вычислимость и логика". То же самое: главы 6 и 7 посвящены вычислениям на абаке - по сути той же машине Шенфилда. О самом Шенфилде - ни слова. Авторы солидные, издательство солидное, не первое издание - ну не могли они не упомянуть Шенфилда
Открываю, наконец, самого Шенфилда и его "Математическую логику"; никакой машины и близко не нахожу.
То, что называется машиной Шенфилда - по сути обычные регистровые машины, рассмотренные не раз и не два в самых различных книгах и курсах. Обычно, сначала описывают машины Тьюринга, потом плавно переходят к тезису Черча после чего рассказывают о регистровых машинах. Вопрос, конечно, риторический, но, может, знатоки матлогики просветят - при чем тут Шенфилд ?

 

Вот, нарыл чуток: http://en.wikipedia.org/wiki/Counter_machine_models
Кстати, забавная подборка

 

del