Как изобрести все - Райан Норт

Другими словами, какой минимальный набор возможных действий для вычисляющей машины? Так получается, что у компьютера нет технической потребности знать, как умножать, поскольку любое умножение можно представить в виде повторяющегося сложения: 10 умножить на 5 то же самое, что добавить 10 к самому себе 5 раз.

Поэтому умножение заменяем сложением:

Вычитание мы убираем тем же самым образом: 10 минус 5 равно 10 плюс –5 (отрицательное число).

Поэтому вычитание тоже заменяем сложением:

И да, деление тоже можно заменить сложением.

Если мы делим 10 на 2, то мы пытаемся узнать, сколько раз 2 умещается в 10.

Можно рассчитать это, прибавляя 2 к самому себе (как мы делали при умножении), но в этот раз отслеживая, сколько двоек мы добавили, пока не добрались до нужного значения. 2 + 2 +2 + 2+ 2 = 10, то есть пять двоек, поэтому 10 разделить на 2 будет 5. Подобная техника работает даже с числами, которые нельзя разделить без остатка: необходимо добавлять до тех пор, пока следующее добавление не приведет вас за пределы числа, в котором вы заинтересованы, а то, что при этом останется, как раз и будет остатком[238].

Отсюда:

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

Разве это не круто, а?

Прежде чем вы попытаетесь изобрести машину для сложения, давайте вернемся немного назад и вспомним пропозициональное исчисление, которое вы придумали в главе 10.13.1. Там вы определили оператор «не», означающий «противоположное тому, что говорится в утверждении». Так что если у нас есть утверждение p, которое истинно, то «не p» (или ¬p) будет, следовательно, ложным.

Что произойдет, если заменить «истинно» на «1», а ложно на «0»?

Ну, у вас есть таблица истинности для p и ¬p, которая выглядит подобным образом (табл. 19)…

Таблица 19. Таблица истинности для p и ¬p

…и которую можно превратить в список ожидаемых входных и выходных состояний бинарной машины – мы называем их «ячейками», – выглядящий следующим образом (табл. 20).

Таблица 20. Узрите же, ибо это первое в мире представление НЕТ-ячейки

Любая машина, получившая определенное значение на входе, выдаст столь же определенное значение на выходе. И совершенно не важно, как этот результат будет получен, что происходит внутри, главное, что она функционирует как НЕТ-ячейка: 1 на входе значит 0 на выходе и наоборот.

Ее можно даже нарисовать в виде схемы (рис. 62).

Рис. 62. Представление НЕТ-ячейки в графическом виде

К этому моменту у вас еще нет ни малейшего представления, как построить эту НЕТ-машину, но по меньшей мере вы знаете, что она предположительно должна делать. Поскольку же вы вовсе не обязаны «создать эту чертову штуку прямо сейчас», то мы можем рассмотреть и другие операции.

Вспомним логический оператор, который вы определили как «и» (или ∧) и который подразумевает, что оба аргумента должны быть истинными для того, чтобы утверждение в целом являлось истинным. Другими словами, «(p ∧ q)» будет истинным только в том случае, если истинны и p, и q, и ложным в любой другой ситуации.

Вот таблица истинности, которая показывает это наглядным образом (табл. 21).

Таблица 21. Таблица истинности для p ∧ q

И точно так же, как и в случае с «не», необходимо трансформировать «истинно» и «ложно» в единицы и нули, чтобы создать первую в мире И-ячейку, которую мы представим следующим образом (табл. 22, рис. 63).

Таблица 22. Входы и выходы для И-ячейки

Единственная деталь головоломки, которой нам не хватает, – это «или», нечто противоположное «и».

Операция «или» между p и q символизируется так (p ∨ q), и «(p ∨ q)» будет истинным в случае, если либо p либо q истинно.

Рис. 63. Представление И-ячейки в графическом виде

Таблица истинности для ИЛИ-ячейки выглядит следующим образом (табл. 23, рис. 64).

Таблица 23. Входы и выходы для ИЛИ-ячейки

Рис. 64. ИЛИ-ячейка

Три базовые ячейки можно использовать для того, чтобы сконструировать более сложные. Например, поставьте НЕТ-ячейку после И-ячейки, и у вас получится НЕТИ-ячейка, выглядящая следующим образом (табл. 24, рис. 65).

Таблица 24. Входы и выходы для НЕТИ-ячейки

Рис. 65. Полная НЕТИ-ячейка