ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ

ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ, абстрактная машина,- математическое понятие, к-рое описывает модель вычислительной машины, абстрагируясь от ограниченности емкости запоминающих устройств и других технич. параметров вычислительных машин. В отличие от последних, В. м. а. может вычислять функции, определенные на бесконечной области конструктивных объектов (напр., целых чисел, слов в конечном алфавите, конечных графов, бесконечных деревьев и т. д.). В. м. а. употребляется как понятие, уточняющее интуитивное понятие алгоритма, для исследования вопросов существования алгоритма (т. е. разрешимости или неразрешимости алгоритмических проблем), качества алгоритма (т. е. оценок сложности различных параметров алгоритма), формализации семантики алгоритмических языков, моделирования одних классов В. м. а. другими (напр., с целью так наз. «распараллеливания» алгоритмов).

В. м. а. можно разделить на классы по уровню абстракции, а также по типу обрабатываемой информации. Ниже перечислены основные классы В. м. а.

1) В. м. а., обрабатывающие слова в конечном алфавите и относящиеся к наиболее высокому уровню абстракции в связи с подчинением структуры В. м. а. специфич. запросам теории. Типичные представители -Тьюринга машина, машины Минского, нормальные алгорифмы Маркова, Поста каноническая система. В. м. а. часто употребляются для доказательства неразрешимости алгоритмич. проблем, а также для оценок сложности алгоритмов (см. Алгоритма сложность вычисления).

2) В. м. а., относящиеся к тому же уровню абстракции, что и В. м. а. из 1-го класса, но обрабатывающие матрицы, конечные графы, произвольные комплексы. Типичные представители - алгоритмы Колмогорова, автоматы Неймана - Чёрча, растущие автоматы. Если в алгоритмах Колмогорова преобразование информации производится локально, то в автоматах Неймана-Чёрча и растущих оно протекает параллельно. Построены универсальные В. м. а. с хорошими характеристиками, способные моделировать произвольные В. м. а. данного типа. Изучались вычисления с максимальным быстродействием (т. е. в реальное время) на В. м. а. из данного класса.

3) В. м. а., к-рые обрабатывают, чаще всего, слова или целые числа и относятся к низкому уровню абстракции. Их структуры сформировались под влиянием запросов практики и имеют много общего со структурами вычислительных машин. Типичные представители - так паз. операторные алгоритмы (см. [3]) и машины с произвольным доступом к памяти. Эти В. м. а. употребляются для оценки сложности алгоритмов, используемых на практике, и для моделирования двух типов В. м. а.

4) В. м. а., относящиеся к тому же уровню абстракции, что и В. м. а. из 3-го класса, но обрабатывающие произвольные графы (чаще всего бесконечные деревья). Эти В. м. а. образовались в результате развития В. м. а. из 3-го класса, направленного на приспособление к особенностям алгоритмич. языков. Такие В. м. а. используются для формализации семантики алгоритмич. языков, а также для доказательства правильности программ. Типичные представители - В. м. а., используемые для задания семантики языков алгол-68 и ПЛ/1.

Лит.: [1] Барздинь Я. М., «Докл. АН СССР», 1964, т. 157, № 3, с. 542-45; [2] Ван Вейнгаарден А. и др., Сообщение об алгоритмическом языке АЛГОЛ-68, «Кибернетика», 1969, № 6, с. 23-144; 1970, № 1, с. 13-160; [3] Ершов А. П., «Проблемы кибернетики», 1960, вып. 3, с. 5-48; [4] Колмогоров А. Н., Успенский В. А., «Успехи матем. наук», 1958, т. 13, № 4, с. 3-28; [5] Минский М., Вычисления и автоматы, пер. с англ., М., 1971; [6] Трахтенброт Б. А., Алгоритмы и вычислительные автоматы, М., 1974; [7] Hartmanis Т., «Math. Syst. Тhеоrу», 1971, v. 5, № 3, p. 232-45; [8] Wegner P., «Computing Surveys», 1972, v. 4, № 1, p. 5-63.

В. А. Непомнящий.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.