Абак

Абак наряду с машинами Тьюринга является одной из простейших универсальных моделей вычислений. Это числовая модель; элементами информации являются целые неотрицательные числа.

Память представляет собой потенциально бесконечный набор ячеек, каждая ячейка может содержать любое целое неотрицательное число. Считается, что ячейки пронумерованы числами .

Исполняющее устройство способно выполнять всего две операции (элементарные команды) над числами, это прибавление (increment) и вычитание (decrement) единицы из указанного в команде числа. Команды имеют вид и , где

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

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

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

Примеры программ. В рассмотренных ниже примерах операция обозначается для краткости через , а операция — через . Основные операции изображены кружками. Прямоугольниками изображены операции, для которых в предыдущих примерах построены алгоритмы. Знак "" на соответствующих дугах опущен. Сформулируйте инварианты циклов во всех рассмотренных ниже примерах.

1. Программа

   В языках программирования эта операция обычно является элементарной. На абаке это действие можно выполнить следующей программой:

2. Программа

3. Программа

4. Программа

5. Программа

6. Программа

7. Программа

Содержание    Вперед

---

---