Решения задач о регистровых машинах

 

 

Упражнение 1

 

программа 1:

 

 

а. Сколько шагов потребуется регистровой машине, чтобы сложить 2 + 5 и получить 7, выполняя программу 1 (считая Кон отдельным шагом)?

 

Ответ: шесть шагов. Три декремента, два инкремента, одно окончание программы (последний декремент – переход на ноль).

 

б. Сколько шагов потребуется машине, чтобы сложить 5 + 2?

 

Ответ: двенадцать шагов. Шесть декрементов, пять инкрементов и одно окончание программы.

 

1 (Какой из этого можно сделать вывод?)

 

Ответ: порядок содержимого может иметь большое значение, так что вам может показаться необходимым ввести правило всегда помещать меньшее число в регистр 1, но, если для этого вам сначала придется сравнивать два числа, чтобы выяснить, какое из них меньше, в итоге вам потребуется больше шагов, чем для сложения!

 

Упражнение 2

 

а. Напишите РПА-программу для этого графа потока. (Обратите внимание: поскольку программа разветвляется, вы можете пронумеровать шаги несколькими способами. Неважно, какой из них вы выберете: главное, чтобы на верные следующие шаги указывали команды безусловного перехода.)

 

 

 

б. Что происходит, когда программа пытается вычесть 3 из 3 или 4 из 4?

 

Программа останавливается с нулем в регистре 4.

 

в. Какая возможная ошибка предотвращается обнулением регистра 3 перед попыткой вычитания на шаге  3 вместо шага 4?

 

Если на старте и в регистре 1, и в регистре 2 были нули, в конце программа могла выдать абсурдный ответ (либо – 0, либо число, отличное от 0 и 1, в регистре знака).

 

Упражнение 3

 

а. Нарисуйте граф потока (и напишите РПА-программу) для умножения содержимого регистра 1 на содержимое регистра 3, поместив ответ в регистр 5.

 

 

б. (По желанию) Используя копирование и перемещение, улучшите программу умножения, созданную в задаче а: когда она закончит работу, изначальное содержимое регистра 1 и регистра 3 восстановится, так что вы сможете легко проверить исходные данные и ответы на правильность по завершении программы.

 

 

 

 

 

 

в. (По желанию) Нарисуйте граф потока и напишите РПА-программу, которая изучает содержимое регистра 1 и регистра 3 (не разрушая их!) и записывает адрес ( 1 или 3 ) регистра с большим содержимым в регистр 2 или помещает 2 в регистр 2, если содержимое регистров 1 и 3 равно. (После выполнения этой программы содержимое регистра 1 и регистра 3 должно остаться неизменным, а регистр 2 должен показывать, равно ли их содержимое, а если нет, то в каком из регистров содержимое больше.)

 

 

 

 

упражнение 4 (по желанию)

 

Нарисуйте граф потока и напишите РПА-программу, которая превращает регистровую машину в простой карманный калькулятор, следующим образом:

 

а. Используйте регистр 2 для операции:

 

0 = ADD

1 = SUBTRACT

2 = MULTIPLY

3 = DIVIDE

 

б. Поместите числа, с которыми будут производиться манипуляции, в регистры 1 и 3.

(Таким образом, 3 0 6 будет означать 3 + 6; 5 1 3 будет означать 5–3; 4 2 5 будет означать 4 * 5; а 9 3 3 будет означать 9 ÷ 3 .) Затем поместите результаты операции в регистры 4–7, используя регистр 4 для знака (где 0 означает +, а 1 означает –), регистр 5 для численного ответа, регистр 6 для возможного остатка в случае деления, а регистр 7 для сообщения об ошибке ввода (либо требовании делить на ноль, либо неопределенной операции в регистре 2 ).

 

 

 

 

 

Источники

 

 

I. Введение

 

Мысленные эксперименты об эксцентричном тюремщике и драгоценностях в урне взяты с переработками из Elbow Room (Dennett 1984a).