Гашков - Системы счисления и их применение

Пусть нам нужно вычислить данную числовую функцию f(x1, ..., xn). Представим себе, что у нас есть счёты, содержащие n <входных> спиц, на i-й из которых имеется в начальный момент xi костяшек, одну <выходную> (первоначально пустую) спицу, на которой будет получен результат, и некоторое количество (первоначально пустых) <рабочих> спиц. Каждая спица состоит на самом деле из двух половин, и пока речь шла только о левых половинах. В правой половине каждой спицы помещается потенциально не ограниченный запас костяшек, и по нашему желанию мы можем сделать в любой момент одну из двух операций: либо передвинуть самую левую костяшку из правой половины спицы

в<рабочую> левую половину, увеличив тем самым <записанное>

вней число на единицу, либо передвинуть крайнюю правую костяшку из <рабочей> левой половины спицы в правую <запасную> половину, уменьшив тем самым <записанное> в левой половине число на единицу.

Если перейти к терминологии языков программирования, то мы здесь описали систему регистров машины, и две операции, применимые к ним — прибавление единицы и вычитание единицы.

Сама программа вычисления на счётах (или на соответствующей идеализированной машине с неограниченными регистрами) представляет из себя диаграмму, состоящую из кружочков, в которых написаны номера спиц (регистров), после которых стоят знаки плюс или минус, указывающие на операции, которые мы выполняем на этих спицах (регистрах). Из кружочков со знаком плюс выходит одна стрелка, ведущая в какой-то другой кружочек (она указывает какую следующую операцию делать). Из кружочков со знаком минус выходит две такие стрелки. Одна из них помечается специальным значком и используется только тогда, когда на <рабочей> половине спицы не осталось костяшек (в регистре записан ноль). Тогда операция вычитания единицы, естественно, не может быть выполнена, и просто делается переход к новой вершине диаграммы по указанной стрелке. Если же на спице оставались костяшки (регистр не равен 0), то операция вычитания единицы выполняется и тоже делается переход к новой вершине диаграммы, но, естественно, по второй стрелке. Отметим ещё, что совсем не обязательно, чтобы разные вершины диаграммы выполняли операции с разными спицами.

Теперь, чтобы такая диаграмма могла определить работающую программу, осталось выделить в ней две стрелки — начало и конец работы программы. Первая из них выделяется среди других стрелок тем, что имеет конец в одной из вершин диаграммы, но не имеет начала в вершинах диаграммы, а начинается в специальном кружке со словом <НАЧАЛО>, а вторая, наоборот, начинается в одной

50

из вершин, но не ведёт ни в одну из вершин диаграммы, а ведёт в кружок со словом <КОНЕЦ>.

Программа начинает работать со слова <НАЧАЛО> и заканчивает, когда придёт в слово <КОНЕЦ> (но может и <зациклиться> и никогда не закончить работу). Результатом работы программы можно считать число, записанное на <выходном> регистре. Если это число всегда совпадает со значением рассматриваемой функции f(x1, ..., xn), в случае, если она определена при заданных значениях переменных, и если программа всегда <зацикливается> в случае, если эта функция не определена при заданных значениях переменных, то говорят, что программа (вычисления на счётах!) правильно вычисляет заданную функцию.

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

Работу любой такой программы можно промоделировать и на машине Тьюринга, если изображать состояние абака в каждый момент времени на ленте машины в виде массивов палочек, разделённых пробелами. В возможность обратного моделирования поверить труднее, тем не менее справедливо следующее утверждение, приводимое без доказательства.

Класс числовых функций, вычислимых на абаке, совпадает

склассом функций, вычислимых по Тьюрингу.

Акак известно, на машине Тьюринга можно промоделировать любые компьютерные вычисления. Значит, и на счётах тоже можно!

31. Приведитепример<зацикливающейся>программыдляабака.

32. Приведите пример программы, складывающей содержимое двух регистров и помещающей результат во второй регистр одновременно с обнулением первого регистра.

33. Приведите пример программы, складывающей содержимое двух регистров и помещающей результат во второй регистр, но не изменяющей первый регистр (используйте вспомогательный <рабочий> регистр).

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

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

36. Покажите, как возводить в степень на счётах. (Используйте предыдущую программу в качестве подпрограммы.)

51

ЛИТЕРАТУРА

Литература по теме книжки огромна, и приводимый далее список не претендует на полноту. В него включены некоторые источники, использованные автором при подготовки книжки, а также расширяющие и дополняющие её. Они выбраны из числа наиболее доступных, в том числе и по времени издания.

[1]Ал футова Н. Б., Усти нов А. В. Алгебра и теория чисел: Сборник задач. — М.: МЦНМО, 2002.

[2]А н д р е е в а Е., Ф а л и н а И. Системы счисления и компьютерные арифметика. — М.: Лаборатория базовых знаний, 1999.

[3]Б у л о с Д., Д ж е ф р и Р. Вычислимость и логика. — М.: Мир, 1994.

[4]В а с и л ь е в Н. Б., Е г о р о в А. А. Задачи всесоюзных математических олимпиад. — М.: Наука, 1988. — (Библиотека

математического кружка. Вып. 18).

[5] В о р о б ь ё в Н. Н. Признаки делимости. — М.: Наука, 1988. — (Популярные лекции по математике. Вып. 39).

[6]Гальпе рин Г. А., Т олп ыг о А. К. Московские математические олимпиады. — М.: Просвещение, 1986.

[7]Г а р д н е р М. Математические головоломки и развлечения / Пер. с англ. Ю. А. Данилова / Под ред. Я. А. Смородинского. — М.: Мир, 1999. — (Математическая мозаика. Вып. 1).

[8]Гарднер М. Математические досуги / Пер. с англ. Ю. А. Данилова / Под ред. Я. А. Смородинского. — М.: Мир, 2000. —

(Математическая мозаика. Вып. 2).

[9] Г а р д н е р М. Математические новеллы / Пер. с англ. Ю. А. Данилова / Под ред. Я. А. Смородинского. — М.: Мир, 2000. — (Математическая мозаика. Вып. 3).

[10]Г а ш к о в С. Б., Ч у б а р и к о в В. Н. Арифметика, алгоритмы, сложность вычислений. — М.: Высшая школа, 2000.

[11]Д ад ае в Ю. Г. Теория арифметических кодов. — М.: Радио и связь, 1981.

[12]Ел е н ьс к и й Щ. По следам Пифагора. — М.: Детгиз, 1961.

[13] К н у т Д. Искусство программирования: Пер. с англ. —

Т. 2. — М.: Вильямс, 2000.

[14]П е т ц о л ь д Ч. Код. — М.: Русская редакция Майкрософт Пресс, 2001.

[15]Севидж Д. Сложность вычислений. — М.: Факториал, 1998.

[16] С т а х о в А. П. Коды золотой пропорции. — М.: Радио

о связь, 1984.

[17]Ф о м и н С. В. Системы счисления. — М.: Наука, 1980. — (Популярные лекции по математике. Вып. 40).

[18] Ш т е й н г а у з Г. Математический калейдоскоп: Пер. с польск. — М.: Наука, 1981. — (Библиотечка <Квант>. Вып. 8).

52

БИБЛИОТЕКА <МАТЕМАТИЧЕСКОЕ ПРОСВЕЩЕНИЕ>