Часто думается, что проблема формализации понятия последовательного алгоритма была решена Чёрчем [1936] и Тьюрингом [1936]. Например, согласно Сэведжу [1987], алгоритм – это вычислительный процесс, определенный машиной Тьюринга. Но Чёрч и Тьюринг не решали проблему формализации понятия последовательного алгоритма. Вместо этого они дали (различные, но эквивалентные) формализации понятия вычислимой функции, и больше относится к алгоритму чем функция, которую он вычисляет.
Ремарка. И Чёрч и Тьюринг интересовались классической проблемой решения (найдите алгоритм, который решает, действительна ли данная формула первого уровня), центральной проблемы логики в то время [Бёргер и др. 1996]. Они использовали формализацию понятия вычислимой функции, чтобы доказать неразрешимость классической проблемы решения. В частности, Тьюринг выдвигал тезис, что каждая вычислимая функция является вычислимой с помощью машиной Тьюринга. Он доказал, что никакая машина Тьюринга не вычисляет верность формул первого уровня. Но тезисом обоснованность не вычислима. Обратите внимание, что формализация Чёрча-Тьюринга либеральна: вычислимая функция Чёрча-Тьюринга может быть невычислимой в любом практическом смысле. Но их формализация делает возможным получения результатов неразрешимости.
Конечно, понятия алгоритма и вычислимой функции глубоко связаны: по определению, вычислимая функция – это функция, вычислимая алгоритмом. И Чёрч и Тьюринг говорили о произвольных алгоритмах. Согласно серьёзному тезису Тьюринга, упомянутому в ремарке, каждый алгоритм может моделироваться машиной Тьюринга. Кроме того, эксперты сложности вычислений, согласны с тем, что любой алгоритм может моделироваться машиной Тьюринга с полиномиальным замедлением. Но машина Тьюринга может работать слишком долго, с ее головкой, ползающей назад и вперед на той бесконечной ленте, чтобы моделировать один шаг данного алгоритма. Полиномиальное замедление может быть недопустимым.
В то время как Тьюринг проанализировал человеческий компьютер, Колмогоров и Успенский [1958] пришли к своей модели машины (машины КУ), анализируя вычисления с точки зрения физики. Каждый бит информации должен быть представлен в физическом пространстве и может иметь только очень много соседних битов. Можно думать о машине КУ как обобщенной машине Тьюринга, где лента – это реконфигурируемый граф ограниченной степени. Машины Тьюринга не могут моделировать машины КУ эффективно [Григорьев 1976]. Колмогоров и Успенский не формулировали никакого тезиса. В докладе, посвящённом памяти о Колмогорове, я попытался сделать это для них: “каждое вычисление, выполняя только одно ограниченное местное действие одновременно, может рассматриваться как (не только быть моделируемым, но и фактически являться) вычислением соответствующей машины КУ" [Gurevich 1988]. Успенский [1992, p. 396] согласился.
Под влиянием Конвейской «Игры Жизни», Ганди [1980] утверждал, что анализ Тьюринга человеческих вычислений не применяется непосредственно к механическим устройствам. Наиболее важно, что механическое устройство может быть параллельным. Ганди выдвигал четыре принципа, которым должна удовлетворить любая такая машина. «Самый важный из них, названный «принципом местной причинной связи», отклоняет возможность мгновенного действия на расстоянии. Хотя принципы выровнены обращением к геометрии пространства-времени, формулировка весьма абстрактна, и может быть применена ко всем видами автоматов и алгебраических систем. Доказано, что, если устройство удовлетворяет принципу, тогда его последовательные состояния формируют вычислимую последовательность.» Работа Ганди вызвала интересное обсуждение в логическом сообществе.
Очевидно не подозревая о машине КУ, Шонэдж [1980] представил свои машины модификации хранения, близко связанные с указательными машинами Кнута [1968, стр. 462 - 463]. Модель машины Шонеджа может быть рассмотрена как обобщение модели КУ, где граф направлен, и только степень исхода вершин ограничена. Это обобщение естественно с точки зрения вычислений указателя на наших компьютерах. С физической точки зрения, не настолько естественно, что к одному узлу можно получить доступ непосредственно неограниченным числом других узлов. В любом случае, уровень абстракции модели Шонеджа выше, чем у модели КУ. Неизвестно, может ли каждая машина Шонеджа быть шаг за шагом промоделирована машиной КУ.
Машины произвольного доступа Кука и Рекхоу [1973] более мощны, чем машины Шонэджа. Дополнительные модели вычисления найдены в [Сэведж 1998].
В приложениях, алгоритм может использовать мощные операции - матричное умножение, дискретные преобразования Фурье, и т.д. - как есть. На уровне абстракции алгоритма, такая операция выполнена в пределах одного шага, и проблема фактического выполнения операции оставлена реализации. Далее, состояние алгоритма высокого уровня не должно быть конечным (что противоречит первому из принципов Ганди). Там существует модель вычисления с абстракциями высокого уровня. Например, модель вычисления Блюма, Шуба, и Смале [1989] работает, непосредственно, с подлинными вещественными числами. Описания параллельных алгоритмов высокого уровня разработаны в [Чанди и Мисра 1988].
Я искал модель машины (со специфическим языком программирования) такую, что любой последовательный алгоритм, например абстрактный, мог бы моделироваться шаг за шагом машиной этой модели. Позвольте называть такую модель универсальной, относительно последовательных алгоритмов. Модель Тьюринга универсальна относительно вычислимых функций, но не относительно алгоритмов. В основном, последовательный тезис АСМ лежит в том, что последовательная модель АСМ является универсальной относительно последовательных алгоритмов. Я не знаю никакую другую попытку придумать модель последовательных алгоритмов, которая является универсальной относительно последовательных алгоритмов в том сильном смысле.
1. Church, A. 1936. An unsolvable problem of elementary number theory. American Journal of Mathematics 58, 345-363.
2. Turing,
A. 1936. On computable numbers, with an application to the Entscheidungs problem. Proceedings of
3.
4. Kolmogorov, A. N. and Uspensky,
V. A. 1958. On the definition of algorithm. Uspekhi Mat. Nauk 13, 4, 3-
5. Grigoriev, D. 1976. Kolmogorov algorithms are stronger than Turing machines. Journal of Soviet Mathematics 14 (1980), 5, 1445-1450.
6. Gurevich, Y. 1988. Kolmogorov machines and related issues. Bulletin of European Association for Theoretical Computer Science, Number 35 (1988), pp. 71-82.
7. Uspensky, V. A. 1992. Kolmogorov and mathematical logic. Journal of Symbolic Logic 57, 2, 385-412.
8. Gandy, R. 1980. Church's thesis and principles for mechanisms. In J. Barwise, H. J. Keisler, and K. Kunen Eds., The Kleene Symposium, pp. 123-148. North-Holland.
9. Schonhage, A. 1980. Storage modi_cation machines.
10. Knuth, D. E. 1968. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.
11. Cook, S. A. and Reckhow, R. A. 1973. Time bounded random access machines. Journal of Computer and Systems Sciences 7, 4, 354-375.
12. Savage, J. E. 1998. Models of Computation: Exploring the Power of Computing. Addison Wesley Longman.
13. Blum, L., Shub, M., and Smale, S. 1989. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of American Mathematical Society 21, 1, 1-46.
14. Chandy, K. M. and Misra, J. 1988. Parallel Program Design. Addison-Wesley.