\input style
\chapter{0 рсёЄЁръЎш▀ шёяюыэхэш▀}

рБСТРАКЦИЯ ИСПОЛНЕНИЯ ЛЕЖИТ В ОСНОВЕ ВСЕГО ПОНЯТИЯ "АЛГОРИТМА" НАСТОЛЬКО 
ГЛУБОКО, ЧТО ОБЫЧНО ЕЕ СЧИТАЮТ САМО СОБОЙ РАЗУМЕЮЩЕЙСЯ И ОСТАВЛЯЮТ БЕЗ
ВНИМАНИЯ. хЕ НАЗНАЧЕНИЕ В ТОМ, ЧТОБЫ СОПОСТАВЛЯТЬ МЕЖДУ СОБОЙ РАЗЛИЧНЫЕ 
ВЫЧИСЛЕНИЯ. шНАЧЕ ГОВОРЯ, ОНА ПРЕДОСТАВЛЯЕТ НАМ СПОСОБ ОСМЫСЛИВАНИЯ
КОНКРЕТНОГО ВЫЧИСЛЕНИЯ КАК ЭЛЕМЕНТА БОЛЬШОГО КЛАССА РАЗЛИЧНЫХ ВЫЧИСЛЕНИЙ; 
МЫ МОЖЕМ ОТВЛЕЧЬСЯ ОТ ВЗАИМНЫХ ОТЛИЧИЙ ЭЛЕМЕНТОВ ТАКОГО КЛАССА И,
РУКОВОДСТВУЯСЬ ОПРЕДЕЛЕНИЕМ КЛАССА В ЦЕЛОМ, ВЫСКАЗЫВАТЬ УТВЕРЖДЕНИЯ, 
ПРИМЕНИМЫЕ К КАЖДОМУ ЕГО ЭЛЕМЕНТУ, А СЛЕДОВАТЕЛЬНО, СПРАВЕДЛИВЫЕ И ДЛЯ
КОНКРЕТНОГО ВЫЧИСЛЕНИЯ, КОТОРОЕ МЫ ХОТИМ РАССМАТРИВАТЬ.

ўТОБЫ РАЗоЯСНИТЬ, ЧТО ПОДРАЗУМЕВАЕТСЯ ПОД "ВЫЧИСЛЕНИЕМ", Я ОПИШУ СЕЙЧАС 
НЕВЫЧИСЛИТЕЛЬНУЮ КОНСТРУКЦИЮ "ПОЛУЧЕНИЯ" (Я ПРЕДНАМЕРЕННО НЕ УПОТРЕБЛЯЮ 
ТЕРМИНА "ВЫЧИСЛЕНИЕ"), НАПРИМЕР, НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ ЧИСЕЛ 111 И 259. 
юНА СОСТОИТ ИЗ ДВУХ КАРТОННЫХ КАРТОЧЕК, РАСПОЛОЖЕННЫХ ОДНА ПОВЕРХ ДРУГОЙ. 
эА ВЕРХНЕЙ КАРТОЧКЕ НАПИСАН ТЕКСТ "$\эюф(111,259)=$".  ўТОБЫ ПОЛУЧИТЬ ОТ 
КОНСТРУКЦИИ ОТВЕТ, МЫ ПОДНИМАЕМ ВЕРХНЮЮ КАРТОЧКУ И КЛАДЕМ ЕЕ СЛЕВА ОТ НИЖНЕЙ, 
НА КОТОРОЙ ТЕПЕРЬ МОЖНО ПРОЧЕСТЬ ТЕКСТ "37".

яРОСТОТА КАРТОЧНОЙ КОНСТРУКЦИИ ЯВЛЯЕТСЯ БОЛЬШИМ ДОСТОИНСТВОМ, НО ОНА ОМРАЧАЕТСЯ 
ДВУМЯ НЕДОСТАТКАМИ --- МЕЛКИМ И КРУПНЫМ. ьЕЛКИЙ НЕДОСТАТОК СОСТОИТ В ТОМ, ЧТО 
ХОТЯ ЭТУ КОНСТРУКЦИЮ МОЖНО В САМОМ ДЕЛЕ ИСПОЛЬЗОВАТЬ ДЛЯ ПОЛУЧЕНИЯ НАИБОЛЬШЕГО 
ОБЩЕГО ДЕЛИТЕЛЯ ЧИСЕЛ 111  И 259, НО ПОМИМО ЭТОГО ОНА МАЛО НА ЧТО ПРИГОДНА. 
юДНАКО КРУПНЫЙ НЕДОСТАТОК В ТОМ, ЧТО, КАК БЫ ТЩАТЕЛЬНО МЫ НИ ПРОВЕРЯЛИ
УСТРОЙСТВО КОНСТРУКЦИИ, НАША ВЕРА В ТО, ЧТО ОНА ВЫРАБАТЫВАЕТ ПРАВИЛЬНЫЙ ОТВЕТ, 
МОЖЕТ ОСНОВЫВАТЬСЯ ТОЛЬКО НА НАШЕМ ДОВЕРИИ К ЕЕ СОЗДАТЕЛЮ: ОН МОГ ОШИБИТЬСЯ 
ЛИБО ПРИ ПРОЕКТИРОВАНИИ СВОЕЙ МАШИНЫ, ЛИБО ПРИ ИЗГОТОВЛЕНИИ НАШЕГО КОНКРЕТНОГО
ЭКЗЕМПЛЯРА.

ўТОБЫ ПРЕОДОЛЕТЬ МЕНЬШЕЕ ЗАТРУДНЕНИЕ, МЫ МОГЛИ БЫ РАССМОТРЕТЬ ИЗОБРАЖЕНИЕ НА 
ОГРОМНОМ ЛИСТЕ КАРТОНА БОЛЬШОГО ПРЯМОУГОЛЬНОГО МАССИВА ИЗ СЕТЕВЫХ ТОЧЕК С
ЦЕЛЫМИ КООРДИНАТАМИ $x$ И $y$,  УДОВЛЕТВОРЯЮЩИМИ ОТНОШЕНИЯМ $0 \le x \le 500$ 
И $0\le y \le 500$. фЛЯ КАЖДОЙ ТАКОЙ ТОЧКИ $(x, y)$ С ПОЛОЖИТЕЛЬНЫМИ 
КООРДИНАТАМИ (Т.~Е. ЗА ИСКЛЮЧЕНИЕМ ТОЧЕК НА ОСЯХ) МЫ  МОЖЕМ ВЫПИСАТЬ В 
СООТВЕТСТВУЮЩЕЙ ПОЗИЦИИ ЗНАЧЕНИЕ $\эюф(x,y)$; ПРЕДЛАГАЕТСЯ ДВУМЕРНАЯ ТАБЛИЦА 
ИЗ $250\,000$ ЭЛЕМЕНТОВ. ё  ТОЧКИ ЗРЕНИЯ ПОЛЕЗНОСТИ ЭТО ЗНАЧИТЕЛЬНОЕ 
УСОВЕРШЕНСТВОВАНИЕ: ВМЕСТО КОНСТРУКЦИИ, СПОСОБНОЙ ВЫДАВАТЬ НАИБОЛЬШИЙ
ОБЩИЙ ДЕЛИТЕЛЬ ЕДИНИЧНОЙ ПАРЫ ЧИСЕЛ, МЫ ИМЕЕМ ТЕПЕРЬ "КОНСТРУКЦИЮ",  СПОСОБНУЮ 
ВЫДАВАТЬ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ ЛЮБОЙ ПАРЫ ИЗ $250\,000$ РАЗЛИЧНЫХ ПАР 
ЧИСЕЛ. ¤ТО МНОГО, НО ОСОБЕННО РАДОВАТЬСЯ НЕЧЕМУ, ТАК КАК УКАЗАННЫЙ РАНЕЕ ВТОРОЙ
НЕДОСТАТОК (ПОЧЕМУ МЫ ДОЛЖНЫ ВЕРИТЬ, ЧТО КОНСТРУКЦИЯ ВЫДАЕТ ПРАВИЛЬНЫЙ ОТВЕТ?) 
ПОМНОЖИЛСЯ НА ТЕ ЖЕ САМЫЕ $250\,000$, И ТЕПЕРЬ ОТ НАС ТРЕБУЕТСЯ УЖЕ СОВСЕМ 
БЕЗГРАНИЧНОЕ ДОВЕРИЕ К ЕЕ ИЗГОТОВИТЕЛЮ. яОЭТОМУ ПЕРЕЙДЕМ К РАССМОТРЕНИЮ ДРУГОЙ 
КОНСТРУКЦИИ. эА ТАКОМ ЖЕ ЛИСТЕ КАРТОНА С СЕТЕВЫМИ ТОЧКАМИ НАПИСАНЫ ТОЛЬКО 
ЧИСЛА, ПРОБЕГАЮЩИЕ ЗНАЧЕНИЯ ОТ 1 ДО 500 ВДОЛЬ ОБЕИХ ОСЕЙ. ъРОМЕ ТОГО, НАЧЕРЧЕНЫ 
СЛЕДУЮЩИЕ ПРЯМЫЕ ЛИНИИ:

1) ВЕРТИКАЛЬНЫЕ ЛИНИИ (С УРАВНЕНИЕМ $x=\var{КОНСТАНТА}$);

2) ГОРИЗОНТАЛЬНЫЕ ЛИНИИ (С УРАВНЕНИЕМ $y=\var{КОНСТАНТА}$);

3) ДИАГОНАЛИ (С УРАВНЕНИЕМ $x+y=\var{КОНСТАНТА}$);

4) "ЛИНИЯ ОТВЕТА" С УРАВНЕНИЕМ $x=y$.

ўТОБЫ РАБОТАТЬ НА ЭТОЙ МАШИНЕ, МЫ ДОЛЖНЫ СЛЕДОВАТЬ СЛЕДУЮЩИМ ИНСТРУКЦИЯМ 
("ИГРАТЬ ПО СЛЕДУЮЩИМ ПРАВИЛАМ"). ъОГДА ХОТИМ НАЙТИ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ 
ДВУХ ЧИСЕЛ $X$ И $Y$, МЫ ПОМЕЩАЕМ ФИШКУ --- ТАКЖЕ ПОСТАВЛЯЕМУЮ 
ИЗГОТОВИТЕЛЕМ --- В СЕТЕВУЮ ТОЧКУ С КООРДИНАТАМИ $x=X$ И $y=Y$. ъОЛЬ СКОРО
ФИШКА НЕ НАХОДИТСЯ НА "ЛИНИИ ОТВЕТА", РАССМАТРИВАЕМ НАИМЕНЬШИЙ РАВНОБЕДРЕННЫЙ
ПРЯМОУГОЛЬНЫЙ ТРЕУГОЛЬНИК, У КОТОРОГО ВЕРШИНА ПРЯМОГО УГЛА СОВПАДАЕТ С ФИШКОЙ, 
А ОДИН ИЗ КОНЦОВ ГИПОТЕНУЗЫ (ЛИБО НИЖЕ ФИШКИ, ЛИБО СЛЕВА ОТ НЕЕ) НАХОДИТСЯ НА 
ОДНОЙ ИЗ ОСЕЙ. (яОСКОЛЬКУ ФИШКА НЕ ЛЕЖИТ НА ЛИНИИ ОТВЕТА, ТАКОЙ ПРЯМОУГОЛЬНЫЙ
ТРЕУГОЛЬНИК БУДЕТ ИМЕТЬ НА ОСЯХ ТОЛЬКО ОДНУ ВЕРШИНУ.) чАТЕМ ФИШКА ПЕРЕМЕЩАЕТСЯ 
В СЕТЕВУЮ ТОЧКУ, СОВПАДАЮЩУЮ С ДРУГИМ КОНЦОМ ГИПОТЕНУЗЫ. ЄАКОЕ ПЕРЕМЕЩЕНИЕ 
ПОВТОРЯЕТСЯ ДО ТЕХ ПОР, ПОКА ФИШКА НЕ ДОСТИГНЕТ ЛИНИИ ОТВЕТА. яОСЛЕ ЭТОГО 
$x$-КООРДИНАТА (ИЛИ  $y$-КООРДИНАТА) ОКОНЧАТЕЛЬНОГО ПОЛОЖЕНИЯ ФИШКИ ЯВЛЯЕТСЯ  
ИСКОМЫМ ОТВЕТОМ.

ъАК НАМ УБЕДИТЬСЯ В ТОМ, ЧТО ЭТА МАШИНА БУДЕТ ВЫДАВАТЬ ПРАВИЛЬНЫЙ РЕЗУЛЬТАТ? 
хСЛИ $(x, y)$ --- ЛЮБАЯ ИЗ $249\,500$ ТОЧЕК НЕ НА ЛИНИИ ОТВЕТА 
И~$(x' y')$ --- ТОЧКА, В КОТОРУЮ ПЕРЕДВИНЕТСЯ ФИШКА ЗА ОДИН ШАГ ИГРЫ, ТО 
ЛИБО~$x'=x$ И~$y'=y-x$, ЛИБО~$x'=x-y$ И~$y'=y$. эЕТРУДНО \emph{ДОКАЗАТЬ}, ЧТО
$\эюф(x, y)=\эюф(x',y')$. тАЖНЫЙ МОМЕНТ ЗДЕСЬ СОСТОИТ В ТОМ, ЧТО 
\emph{ОДНО И ТО ЖЕ} РАССУЖДЕНИЕ ПРИМЕНЯЕТСЯ ОДИНАКОВО ВЕРНО К ЛЮБОМУ ИЗ 
ВОЗМОЖНЫХ ШАГОВ! ъРОМЕ ТОГО, --- И ОПЯТЬ-ТАКИ БЕЗ ТРУДА --- МЫ МОЖЕМ 
\emph{ДОКАЗАТЬ} ДЛЯ ЛЮБОЙ ТОЧКИ~$(x,y)$ ГДЕ $x=y$ (Т.Е. $(x,y)$ ЯВЛЯЕТСЯ 
ОДНОЙ ИЗ 500 ТОЧЕК НА ЛИНИИ ОТВЕТА), ЧТО $\эюф(x,y)=x$. ш СНОВА ВАЖНЫЙ МОМЕНТ 
В ТОМ, ЧТО \emph{ОДИНАКОВОЕ} РАССУЖДЕНИЕ ПРИМЕНИМО К \emph{ЛЮБОЙ} ИЗ 500 ТОЧЕК
НА ЛИНИИ ОТВЕТА. т-ТРЕТЬИХ,--- И ВНОВЬ ЭТО НЕ СОСТАВИТ ТРУДА --- НАМ НУЖНО 
ПОКАЗАТЬ, ЧТО ПРИ ЛЮБОМ ИСХОДНОМ ПОЛОЖЕНИИ $(X, Y)$ КОНЕЧНОЕ ЧИСЛО ШАГОВ В 
САМОМ ДЕЛЕ ПЕРЕНЕСЕТ ФИШКУ НА ЛИНИЮ ОТВЕТА, И ОПЯТЬ ВАЖНО ОТМЕТИТЬ, ЧТО ОДНО 
И ТО ЖЕ РАССУЖДЕНИЕ ОДИНАКОВО ПРИМЕНИМО К ЛЮБОМУ ИЗ $250\,000$ ИСХОДНЫХ 
ПОЛОЖЕНИЙ $(X, Y)$. ЄРИ ПРОСТЫХ РАССУЖДЕНИЯ, ПРОСТРАННОСТЬ КОТОРЫХ НЕ
ЗАВИСИТ ОТ ЧИСЛА СЕТЕВЫХ ТОЧЕК: ЭТА МИНИАТЮРА ПОКАЗЫВАЕТ, НАСКОЛЬКО ВЕЛИКИ 
ВОЗМОЖНОСТИ МАТЕМАТИКИ. хСЛИ ОБОЗНАЧИТЬ ЧЕРЕЗ $(x, y)$ ПРОИЗВОЛЬНОЕ ПОЛОЖЕНИЕ 
ФИШКИ НА ПРОТЯЖЕНИИ ИГРЫ, НАЧАТОЙ В ПОЛОЖЕНИИ $(X, Y)$, ТО ПЕРВАЯ НАША ТЕОРЕМА 
ПОЗВОЛЯЕТ УТВЕРЖДАТЬ, ЧТО ВО ВРЕМЯ ЭТОЙ ИГРЫ ОТНОШЕНИЕ $\эюф(x, y) =\эюф(X, Y)$
БУДЕТ ВСЕГДА СПРАВЕДЛИВО, ИЛИ --- ВЫРАЖАЯСЬ НА СООТВЕТСТВУЩЕМ 
ЖАРГОНЕ --- "ОНО СОХРАНЯЕТ ИНВАРИАНТНОСТЬ". фАЛЕЕ, ВТОРАЯ ТОРЕМА ГЛАСИТ, ЧТО
МЫ МОЖЕМ ИНТЕРПРЕТИРОВАТЬ $x$-КООРДИНАТУ ОКОНЧАТЕЛЬНОГО ПОЛОЖЕНИЯ ФИШКИ КАК 
ТРЕБУЕМЫЙ ОТВЕТ, А ТРЕТЬЯ ТЕОРЕМА ГЛАСИТ, ЧТО ТАКОЕ ОКОНЧАТЕЛЬНОЕ ПОЛОЖЕНИЕ 
СУЩЕСТВУЕТ (Т. Е. БУДЕТ ДОСТИГНУТО ЗА КОНЕЧНОЕ ЧИСЛО ШАГОВ)  ш ЭТИМ ЗАВЕРШАЕТСЯ 
АНАЛИЗ ТОГО, ЧТО МЫ МОГЛИ БЫ НАЗВАТЬ "НАШЕЙ АБСТРАКТНОЙ МАШИНОЙ".

ЄЕПЕРЬ НАМ ОСТАЕТСЯ УБЕДИТЬСЯ В ТОМ, ЧТО ЛИСТ, ПОСТУПИВШИЙ ОТ ИЗГОТОВИТЕЛЯ, 
ЯВЛЯЕТСЯ НА САМОМ ДЕЛЕ ПРАВИЛЬНОЙ МОДЕЛЬЮ АБСТРАКТНОЙ МАШИНЫ. фЛЯ ЭТОГО НУЖНО 
ПРОВЕРИТЬ НУМЕРАЦИЮ ВДОЛЬ ОБЕИХ ОСЕЙ, А ТАКЖЕ ПРОВЕРИТЬ, ПРАВИЛЬНО ЛИ ПРОВЕДЕНЫ 
ВСЕ ПРЯМЫЕ ЛИНИИ. ¤ТО НЕСКОЛЬКО ЗАТРУДНИТЕЛЬНО, ТАК КАК ПРЕДСТОИТ ИССЛЕДОВАТЬ 
ОБоЕКТЫ, ЧИСЛО КОТОРЫХ ПРОПОРЦИОНАЛЬНО $N$, ГДЕ $N$ (В НАШЕМ ПРИМЕРЕ 
500) --- ДЛИНА СТОРОНЫ КВАДРАТА,  НО ВСЕ ЖЕ ПРЕДПОЧТИТЕЛЬНЕЕ, ЧЕМ $N^2$, 
ЧИСЛО ВОЗМОЖНЫХ ВАРИАНТОВ ВЫЧИСЛЕНИЯ.

фРУГАЯ МАШИНА МОГЛА БЫ РАБОТАТЬ НЕ С ОГРОМНЫМ ЛИСТОМ КАРТОНА, А С ДВУМЯ 
ДЕВЯТИБИТОВЫМИ РЕГИСТРАМИ, В КАЖДОМ ИЗ КОТОРЫХ МОЖНО ЗАПОМНИТЬ ДВОИЧНОЕ ЧИСЛО
ОТ~0 ДО~500. яРИ ЭТОМ МЫ МОГЛИ БЫ ИСПОЛЬЗОВАТЬ ОДИН РЕГИСТР ДЛЯ ЗАПОМИНАНИЯ 
ЗНАЧЕНИЯ $x$-КООРДИНАТЫ, А ДРУГОЙ --- ДЛЯ ЗАПОМИНАНИЯ ЗНАЧЕНИЯ $y$-КООРДИНАТЫ, 
СООТВЕТСТВУЮЩЕЙ "ТЕКУЩЕМУ ПОЛОЖЕНИЮ ФИШКИ". яЕРЕМЕЩЕНИЕ ТОГДА СООТВЕТСТВУЕТ
УМЕНЬШЕНИЮ СОДЕРЖИМОГО ОДНОГО РЕГИСТРА НА СОДЕРЖИМОЕ ДРУГОГО. ьЫ МОГЛИ БЫ 
РЕАЛИЗОВАТЬ АРИФМЕТИКУ САМОСТОЯТЕЛЬНО, НО, РАЗУМЕЕТСЯ, ЛУЧШЕ, ЕСЛИ МАШИНА  
СМОЖЕТ ДЕЛАТЬ ЭТО ЗА НАС. хСЛИ МЫ ЗАХОТИМ ПОЛАГАТЬСЯ НА ПОЛУЧЕННЫЙ ОТВЕТ, 
ТО НАМ НУЖНО УМЕТЬ УБЕЖДАТЬСЯ В ТОМ, ЧТО МАШИНА ПРАВИЛЬНО ВЫПОЛНЯЕТ ОПЕРАЦИИ 
СРАВНЕНИЯ И ВЫЧИТАНИЯ. т УМЕНЬШЕННОМ МАСШТАБЕ ПОВТОРЯЕТСЯ ТА ЖЕ ИСТОРИЯ: МЫ
ВЫВОДИМ ЕДИНОЖДЫ И НА ВСЕ СЛУЧАИ, Т.Е ДЛЯ ЛЮБОЙ ПАРЫ $n$-РАЗРЯДНЫХ ДВОИЧНЫХ 
ЧИСЕЛ, УРАВНЕНИЯ ДЛЯ УСТРОЙСТВА ДВОИЧНОГО ВЫЧИТАНИЯ, А ЗАТЕМ УДОСТОВЕРЯЕМСЯ 
В  ТОМ, ЧТО НАША ФИЗИЧЕСКАЯ МАШИНА ПРАВИЛЬНО МОДЕЛИРУЕТ ЭТО АБСТРАКТНОЕ 
УСТРОЙСТВО. хСЛИ ЭТО УСТРОЙСТВО ПАРАЛЛЕЛЬНОГО ВЫЧИТАНИЯ, ТО ЧИСЛО
ПРОВЕРОК --- ПРОПОРЦИОНАЛЬНОЕ ЧИСЛУ ЭЛЕМЕНТОВ И ИХ 
ВЗАИМОСВЯЗЕЙ --- ПРОПОРЦИОНАЛЬНО ЗНАЧЕНИЮ $n=\log_2N$. т ПОСЛЕДОВАТЕЛЬНОЙ 
МАШИНЕ СДЕЛАН ЕЩЕ ОДИН ШАГ НА ПУТИ УПРОЩЕНИЯ ОБОРУДОВАНИЯ ЗА СЧЕТ РАСХОДА 
ВРЕМЕНИ.

ЄЕПЕРЬ Я ПОПЫТАЮСЬ, ХОТЬ БЫ ДЛЯ СВОЕГО СОБСТВЕННОГО ПРОСВЕЩЕНИЯ, УЛОВИТЬ 
ОСНОВНОЙ СМЫСЛ ПРИВЕДЕННОГО ПРИМЕРА.

тМЕСТО ТОГО ЧТОБЫ РАССМАТРИВАТЬ ОДИНОЧНУЮ ПРОБЛЕМУ ВЫЧИСЛЕНИЯ 
$\эюф (111, 259)$, МЫ ОБОБЩИЛИ ЕЕ И ПОДОШЛИ КАК К ЧАСТНОМУ СЛУЧАЮ БОЛЕЕ 
ШИРОКОГО КЛАССА ПpoБЛeМ ВЫЧИСЛЕНИЯ $\эюф(X, Y)$, ёТОИТ ОТМЕТИТЬ, ЧТО МЫ МОГЛИ  
БЫ ОБОБЩИТЬ ПРОБЛЕМУ ВЫЧИСЛЕНИЯ $\эюф(111, 259)$ ПО-РАЗНОМУ: МОЖНО БЫЛО
БЫ РАССМАТРИВАТЬ ЭТУ ЗАДАЧУ КАК ЧАСТНЫЙ СЛУЧАЙ ИНОГО, БОЛЕЕ ШИРОКОГО КЛАССА 
ЗАДАЧ, НАПРИМЕР ВЫЧИСЛЕНИЯ $\эюф(111,259)$, $\эюъ(111,259)$, $111\times259$, 
$111+259$, $111/259$, $111-259$, $111^{259}$, ДНЯ НЕДЕЛИ ДЛЯ 111-ГО ДНЯ 
259-ГО ГОДА НАШЕЙ ЭРЫ И Т. Д. т РЕЗУЛЬТАТЕ МОГ БЫ ПОЯВИТЬСЯ "ПРОЦЕССОР 
ДЛЯ~111 И~259", И ДЛЯ ТОГО, ЧТОБЫ ОН ВЫДАЛ УПОМЯНУТЫЙ ВЫШЕ ОТВЕТ, НАМ 
СЛЕДОВАЛО БЫ ДАТЬ НА ЕГО ВХОД КОМАНДУ "эюф, ПОЖАЛУЙСТА". тМЕСТО ЭТОГО МЫ 
ПРЕДЛОЖИЛИ "эюф-ВЫЧИСЛИТЕЛЬ", КОТОРОМУ ДЛЯ ПОЛУЧЕНИЯ ЭТОГО ОТВЕТА ПОТРЕБУЕТСЯ 
ЗАДАТЬ НА ВХОД ПАРУ ЧИСЕЛ "111, 259" И ЭТО СОВСЕМ ДРУГАЯ МАШИНА!

фРУГИМИ СЛОВАМИ, КОГДА ТРЕБУЕТСЯ ВЫРАБОТАТЬ ОДИН ИЛИ НЕСКОЛЬКО РЕЗУЛЬТАТОВ, 
ОБЫЧНАЯ ПРАКТИКА СОСТОИТ В ТОМ,  ЧТОБЫ ОБОБЩИТЬ ПРОБЛЕМУ И РАССМАТРИВАТЬ ЭТИ
РЕЗУЛЬТАТЫ КАК ЧАСТНЫЕ СЛУЧАИ НЕКОЕГО БОЛЕЕ ШИРОКОГО КЛАССА. юДНАКО МАЛО 
РАДОСТИ, ЕСЛИ ОГРАНИЧИТЬСЯ УТВЕРЖДЕНИЕМ, ЧТО ЛЮБОЙ ПРЕДМЕТ ЯВЛЯЕТСЯ ЧАСТНЫМ 
СЛУЧАЕМ ЧЕГО-ТО БОЛЕЕ ОБЩЕГО. хСЛИ МЫ ХОТИМ СЛЕДОВАТЬ ЭТОМУ ПОДХОДУ, ТО НА 
НАС ВОЗЛАГАЮТСЯ ДВЕ ОБЯЗАННОСТИ:

\medskip
\item{1.} ьЫ ДОЛЖНЫ ИМЕТЬ ПОЛНУЮ ЯСНОСТЬ ОТНОСИТЕЛЬНО СПОСОБА ОБОБЩЕНИЯ, 
Т.~Е. ДОЛЖНЫ ТЩАТЕЛЬНО ВЫБРАТЬ И ЯВНО ОПРЕДЕЛИТЬ БОЛЕЕ ШИРОКИЙ КЛАСС, ПОСКОЛЬКУ
НАШИ РАССУЖДЕНИЯ ДОЛЖНЫ ПРИМЕНЯТЬСЯ КО ВСЕМУ ЭТОМУ КЛАССУ.

\item{2.} ьЫ  ДОЛЖНЫ ВЫБРАТЬ ("ИЗОБРЕСТИ", ЕСЛИ ВАМ УГОДНО) ТАКОЕ ОБОБЩЕНИЕ, 
КОТОРОЕ ОКАЖЕТСЯ ПОЛЕЗНЫМ ДЛЯ НАШИХ ЦЕЛЕЙ.
\medskip

т НАШЕМ ПРИМЕРЕ Я, РАЗУМЕЕТСЯ, ОТДАЮ ПРЕДПОЧТЕНИЕ "эюф-ВЫЧИСЛИТЕЛЮ", А 
НЕ "ПРОЦЕССОРУ ДЛЯ~111 И~259", И СРАВНЕНИЕ ЭТИХ ДВУХ КОНСТРУКЦИЙ ДАЕТ НАМ
НАМЕК НА ТО, КАКИЕ ХАРАКТЕРИСТИКИ ДЕЛАЮТ ОБОБЩЕНИЕ "ПОЛЕЗНЫМ ДЛЯ НАШИХ ЦЕЛЕЙ". 
ьАШИНА, КОТОРАЯ ПО КОМАНДЕ МОЖЕТ ВЫРАБАТЫВАТЬ В КАЧЕСТВЕ ОТВЕТА
ЗНАЧЕНИЯ ВСЕХ ВИДОВ ЗАБАВНЫХ ФУНКЦИЙ ОТ 111 И~259, СТАНОВИТСЯ ВСЕ БОЛЕЕ 
НЕУДОБНОЙ ДЛЯ ПРОВЕРКИ ПО МЕРЕ ТОГО, КАК РАСТЕТ НАБОР ФУНКЦИЙ. т ЭТОМ ЯВНЫЙ
КОНТРАСТ С НАШИМ "эюф-ВЫЧИСЛИТЕЛЕМ".

эюф-ВЫЧИСЛИТЕЛЬ БЫЛ БЫ СТОЛЬ ЖЕ ПЛОХ, ЕСЛИ БЫ ОН ПРЕДСТАВЛЯЛ СОБОЙ ТАБЛИЦУ 
ИЗ $250\,000$ ЗАПИСЕЙ, СОДЕРЖАЩИХ "ЗАГОТОВЛЕННЫЕ" ОТВЕТЫ. хГО ХАРАКТЕРНОЕ
ОТЛИЧИЕ В ТОМ, ЧТО ОН МОЖЕТ БЫТЬ ЗАДАН В ФОРМЕ КОМПАКТНОГО НАБОРА 
"ПРАВИЛ ИГРЫ", КОТОРЫЙ, ЕСЛИ ИГРАТЬ В СООТВЕТСТВИИ С ЭТИМИ ПРАВИЛАМИ, 
ОБЕСПЕЧИТ ВЫДАЧУ НУЖНОГО ОТВЕТА.

юГРОМНЫЙ ВЫИГРЫШ СОСТОИТ В ТОМ, ЧТО ЕДИНОЕ РАССУЖДЕНИЕ ПРИМЕНИТЕЛЬНО К ЭТИМ 
ПРАВИЛАМ ПОЗВОЛЯЕТ НАМ ДОКАЗЫВАТЬ СУЩЕСТВЕННЫЕ УТВЕРЖДЕНИЯ О РЕЗУЛЬТАТАХ
ЛЮБОГО ВАРИАНТА ИГРЫ. ¤ТО ДОСТИГАЕТСЯ ЦЕНОЙ ТОГО, ЧТО ПРИ КАЖДОМ 
ИЗ $250\,000$ КОНКРЕТНЫХ ПРИМЕНЕНИЙ ЭТИХ ПРАВИЛ МЫ ПОЛУЧАЕМ ОТВЕТ "НЕ СРАЗУ": 
КАЖДЫЙ РАЗ ИГРА ДОЛЖНА БЫТЬ СЫГРАНА В СООТВЕТСТВИИ С ПРАВИЛАМИ!

ЄОТ ФАКТ, ЧТО МЫ В СОСТОЯНИИ ДАТЬ СТОЛЬ КОМПАКТНУЮ ФОРМУЛИРОВКУ ПРАВИЛ ИГРЫ, 
КОГДА ЕДИНОЕ РАССУЖДЕНИЕ ПОЗВОЛЯЕТ НАМ ВЫВОДИТЬ ЗАКЛЮЧЕНИЯ О ЛЮБЫХ
ВАРИАНТАХ ИГРЫ, НЕПОСРЕДСТВЕННО СВЯЗАН С СИСТЕМАТИЗИРОВАННЫМ РАСПОЛОЖЕНИЕМ 
$250\,000$ УЗЛОВЫХ ТОЧЕК. ьЫ ОКАЗАЛИСЬ БЫ БЕСПОМОЩНЫМИ, ЕСЛИ БЫ ЛИСТ КАРТОНА 
СОДЕРЖАЛ БЕСПОРЯДОЧНЫЙ СЛУЧАЙНЫЙ РАЗБРОС ТОЧЕК, ИСКЛЮЧАЮЩИЙ КАКУЮ-ЛИБО
СИСТЕМАТИЗАЦИЮ. т НАШЕМ СЛУЧАЕ МЫ МОГЛИ БЫ РАЗДЕЛИТЬ СВОЮ ФИШКУ НА ДВЕ 
ПОЛОВИНКИ И ДВИГАТЬ ОДНУ ПОЛОВИНКУ ВНИЗ, ПОКА ОНА НЕ ЛЯЖЕТ НА ГОРИЗОНТАЛЬНУЮ 
ОСЬ, А ДРУГУЮ ПОЛОВИНКУ ВЛЕВО, ПОКА ОНА НЕ ЛЯЖЕТ НА ВЕРТИКАЛЬНУЮ ОСЬ. тМЕСТО 
ТОГО ЧТОБЫ ВОСПРОИЗВОДИТЬ С ОДНОЙ ФИШКОЙ 250 000 ВОЗМОЖНЫХ ПОЛОЖЕНИЙ, МЫ МОГЛИ 
ДОБИТЬСЯ ТОГО ЖЕ С ДВУМЯ ФИШКАМИ, ДЛЯ КАЖДОЙ ИЗ КОТОРЫХ НУЖНО ТОЛЬКО 500 
ВОЗМОЖНЫХ ПОЛОЖЕНИЙ, Т.~Е. ВСЕГО 1000 ПОЛОЖЕНИЙ В ОБЩЕЙ СЛОЖНОСТИ. ьЫ БЫ 
ДОСТИГЛИ ТОГО ЖЕ УРОВНЯ В $250\,000$ ПОЗИЦИЙ, ИСПОЛЬЗУЯ ТО ОБСТОЯТЕЛЬСТВО, 
ЧТО ЛЮБОЕ ИЗ 500 ПОЛОЖЕНИЙ ОДНОЙ ПОЛОВИНКИ ФИШКИ МОЖЕТ КОМБИНИРОВАТЬСЯ  С 
ЛЮБЫМ ИЗ 500 ПОЛОЖЕНИЙ ДРУГОЙ ПОЛОВИНКИ: ЧИСЛО ПОЛОЖЕНИЙ НЕРАЗДЕЛЕННОЙ ФИШКИ 
РАВНО ПРОИЗВЕДЕНИЮ ЧИСЛА ПОЛОЖЕНИЙ ОДНОЙ ПОЛОВИНКИ НА ЧИСЛО ПОЛОЖЕНИЙ
ДРУГОЙ. эА ПРИНЯТОМ ЖАРГОНЕ МЫ ГОВОРИМ, ЧТО "ОБЩЕЕ ПРОСТРАНСТВО СОСТОЯНИЙ 
РАССМАТРИВАЕТСЯ КАК ДЕКАРТОВО ПРОИЗВЕДЕНИЕ  ПРОСТРАНСТВ СОСТОЯНИЙ
ПЕРЕМЕННЫХ $x$ И~$y$".

тОЗМОЖНОСТЬ ЗАМЕНЫ ОДНОЙ ФИШКИ С ДВУМЕРНОЙ СВОБОДОЙ ВЫБОРА ПОЛОЖЕНИЯ НА ДВЕ 
ПОЛОВИНКИ С ОДНОМЕРНОЙ СВОБОДОЙ ИСПОЛЬЗУЕТСЯ В ПРЕДЛОЖЕННОЙ ВЫШЕ 
ДВУХРЕГИСТРОВОЙ МАШИНЕ. ё ТОЧКИ ЗРЕНИЯ ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ ЭТО
ПРЕДСТАВЛЯЕТСЯ ВЕСЬМА ЗАМАНЧИВЫМ: ТРЕБУЕТСЯ ТОЛЬКО ПОСТРОИТЬ РЕГИСТРЫ, 
СПОСОБНЫЕ РАЗЛИЧАТЬ 500 РАЗНЫХ СЛУЧАЕВ ("ЗНАЧЕНИЙ"), А ЗА СЧЕТ ПРОСТОГО
ОБоЕДИНЕНИЯ ЭТИХ ДВУХ РЕГИСТРОВ ОБЩЕЕ ЧИСЛО РАЗНЫХ СЛУЧАЕВ ВОЗВОДИТСЯ В 
КВАДРАТ! ¤ТО ПЕРЕМНОЖИТЕЛЬНОЕ ПРАВИЛО ПОЗВОЛЯЕТ НАМ РАЗЛИЧАТЬ ГРОМАДНОЕ ЧИСЛО
ВОЗМОЖНЫХ ОБЩИХ СОСТОЯНИЙ С ПОМОЩЬЮ ОГРАНИЧЕННОГО ЧИСЛА КОМПОНЕНТОВ, У КАЖДОГО 
ИЗ КОТОРЫХ ТОЛЬКО ОГРАНИЧЕННОЕ ЧИСЛО ВОЗМОЖНЫХ СОСТОЯНИЙ. яО МЕРЕ
ДОБАВЛЕНИЯ ТАКИХ КОМПОНЕНТОВ РАЗМЕР ПРОСТРАНСТВА СОСТОЯНИЙ ВОЗРАСТАЕТ 
ЭКСПОНЕНЦИАЛЬНО, НО НАМ СЛЕДУЕТ ИМЕТЬ В ВИДУ, ЧТО ЭТО ДОПУСТИМО ТОЛЬКО ПРИ
УСЛОВИИ, ЧТО ОБОСНОВАНИЕ НАШЕГО НОВОВВЕДЕНИЯ ОСТАЕТСЯ ВЕСЬМА КОМПАКТНЫМ; 
ЕСЛИ ТАКОЕ ОБОСНОВАНИЕ ТОЖЕ ВОЗРАСТАЕТ ЭКСПОНЕНЦИАЛЬНО, ТО ВООБЩЕ НЕТ
НИКАКОГО СМЫСЛА СОЗДАВАТЬ ТАКУЮ МАШИНУ.

{\sl чАМЕЧАНИЕ.} єБЕДИТЕЛЬНУЮ ИЛЛЮСТРАЦИЮ К СКАЗАННОМУ ВЫШЕ МОЖНО НАЙТИ 
В ИЗОБРЕТЕНИИ, ВОЗРАСТ КОТОРОГО УЖЕ ПРЕВЫСИЛ ДЕСЯТЬ ВЕКОВ: В ДЕСЯТИЧНОЙ
СИСТЕМЕ СЧИСЛЕНИЯ! юНА ОБЛАДАЕТ ТЕМ ПОИСТИНЕ ПЛЕНИТЕЛЬНЫМ СВОЙСТВОМ, ЧТО 
ЧИСЛО НЕОБХОДИМЫХ ЦИФР ВОЗРАСТАЕТ ВСЕГО ЛИШЬ ПРОПОРЦИОНАЛЬНО ЛОГАРИФМУ
МАКСИМАЛЬНОГО ИЗ ЧИСЕЛ, КОТОРЫЕ ДОЛЖНЫ БЫТЬ ПРЕДСТАВЛЕНЫ. фВОИЧНАЯ СИСТЕМА 
СЧИСЛЕНИЯ --- ЭТО ТО, ЧТО ПОЛУЧАЕТСЯ, КОГДА ВЫ ЗАБЫВАЕТЕ, ЧТО НА КАЖДОЙ РУКЕ 
ИМЕЕТСЯ ПО ПЯТИ ПАЛЬЦЕВ. {\sl(ъОНЕЦ ЗАМЕЧАНИЯ.)}

тЫШЕ МЫ ЗАНИМАЛИСЬ ОДНИМ АСПЕКТОМ МНОЖЕСТВЕННОСТИ, А ИМЕННО БОЛЬШИМ ЧИСЛОМ 
ПОЗИЦИЙ ФИШКИ (= ВОЗМОЖНЫХ СОСТОЯНИЙ). шМЕЕТСЯ ЕЩЕ ОДНА АНАЛОГИЧНАЯ
МНОЖЕСТВЕННОСТЬ, А ИМЕННО БОЛЬШОЕ ЧИСЛО РАЗЛИЧНЫХ ИГР (= ВЫЧИСЛЕНИЙ), 
КОТОРЫЕ МОГУТ СОСТОЯТЬСЯ В СООТВЕТСТВИИ С НАШИМИ ПРАВИЛАЛАМИ ИГРЫ: ПО ОДНОЙ
ИГРЕ ДЛЯ КАЖДОГО НАЧАЛЬНОГО ПОЛОЖЕНИЯ, ЕСЛИ ГОВОРИТЬ ТОЧНЕЕ. эАШИ ПРАВИЛА ИГРЫ 
ЯВЛЯЮТСЯ ОЧЕНЬ ОБЩИМИ В ТОМ СМЫСЛЕ, ЧТО ОНИ ПРИМЕНИМЫ К ЛЮБОМУ НАЧАЛЬНОМУ 
ПОЛОЖЕНИЮ. эО МЫ НАСТАИВАЕМ НА КОМПАКТНОСТИ ОБОСНОВАНИЯ ПРАВИЛ ИГРЫ, А ЭТО
ОЗНАЧАЕТ, ЧТО И САМИ ПРАВИЛА ДОЛЖНЫ БЫТЬ КОМПАКТНЫМИ. т НАШЕМ ПРИМЕРЕ ЭТО 
ДОСТИГАЛОСЬ СЛЕДУЮЩИМ ПРИЕМОМ: ВМЕСТО ПЕРЕЧИСЛЕНИЯ "СДЕЛАЙ ЭТО, СДЕЛАЙ ТО" 
МЫ ЗАДАЛИ ПРАВИЛА ИГРЫ В ВИДЕ ПРАВИЛ ДЛЯ ВЫПОЛНЕНИЯ "ШАГА" В  СОЧЕТАНИИ С
КРИТЕРИЕМ ТОГО, ДОЛЖЕН ЛИ "ШАГ" БЫТЬ ВЫПОЛНЕН В СЛЕДУЮЩИЙ РАЗ. 
(эА САМОМ ДЕЛЕ ШАГ ДОЛЖЕН ПОВТОРЯТЬСЯ, ПОКА НЕ БУДЕТ ДОСТИГНУТО СОСТОЯНИЕ, В
КОТОРОМ ОН СТАНОВИТСЯ НЕОПРЕДЕЛЕННЫМ.) шНАЧЕ ГОВОРЯ, ДАЖЕ ВСЮ ИГРУ ОТ НАЧАЛА 
ДО КОНЦА МОЖНО ПРОИЗВЕСТИ С ПОМОЩЬЮ ПОВТОРЯЕМЫХ ПРИМЕНЕНИЙ ОДНОГО
И ТОГО ЖЕ "ПОДПРАВИЛА".

¤ТО ОЧЕНЬ ПРОДУКТИВНЫЙ ПРИЕМ. юДИН АЛГОРИТМ ЗАКЛЮЧАЕТ В СЕБЕ ПРОЕКТ 
ОПРЕДЕЛЕННОГО КЛАССА ВЫЧИСЛЕНИЙ, КОТОРЫЕ МОГУТ ВЫПОЛНЯТЬСЯ ПОД ЕГО 
УПРАВЛЕНИЕМ; БЛАГОДАРЯ УСЛОВНОМУ ПОВТОРЕНИЮ "ШАГА", ВЫЧИСЛЕНИЯ
ИЗ ТАКОГО КЛАССА МОГУТ ИМЕТЬ РАЗЛИЧНЫЕ ПРОТЯЖЕННОСТИ. ¤ТИМ ОБоЯСНЯЕТСЯ, 
КАК КОРОТКИЙ АЛГОРИТМ МОЖЕТ ЗАНИМАТЬ МАШИНУ В ТЕЧЕНИЕ ДЛИТЕЛЬНОГО ВРЕМЕНИ. 
ё ДРУГОЙ СТОРОНЫ, В ЭТОМ МОЖНО УСМОТРЕТЬ НАЧАЛЬНЫЙ НАМЕК НА ТО, ЗАЧЕМ НАМ
МОГУТ ПОНАДОБИТЬСЯ ОСОБЕННО БЫСТРЫЕ МАШИНЫ.

ьЕНЯ ЗАВОРАЖИВАЕТ МЫСЛЬ, ЧТО ЭТА ГЛАВА МОГЛА ПИСАТЬСЯ ЕЩЕ В ВРЕМЕНА, 
КОГДА хВКЛИД МОГ СМОТРЕТЬ НА НЕЕ ИЗ-ЗА МОЕГО ПЛЕЧА.
\bye