МАШИНА

(в математике) - абстрактное устройство, осуществляющее переработку информации. Употребительны также термины "абстрактная машина", "автомат". Абстрактные М. являются частным случаем управляющих систем. Возникновение их связано с анализом понятия алгоритма, начавшегося в середине 30-х гг. 20 в., с развитием ЭВМ и с построением математич. моделей биологич. систем. Наибольшее распространение получили М., перерабатывающие дискретную информацию, типичными представителями к-рых являются автомат конечный и Тьюринга машина. Абстрактные М. обладают большой наглядностью, возможностью легко осуществлять различные композиции, элементарностью шагов работы. Изучение М. проводится в рамках алгоритмов теории, математич. кибернетики и преследует цели анализа и формализации понятия алгоритма, математич. моделирования реальных устройств и процессов. Существует плодотворная связь между абстрактными М. и реально существующими ЭВМ.

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

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

потенциально неограниченную внешнюю память и устройства для считывания и записывания информации во внешнюю память. Считывание (записывание) информации происходит, как правило, локальным образом. Функционирование М. определяется программой, к-рая состоит из команд вида , где - состояния управляющего устройства, а- упорядоченная информация локального характера из внешней памяти, b- запись изменений содержимого внешней памяти и положения считывающих устройств в ней. Работа М. протекает в дискретном времени. На каждом шаге tработы М. из внешней памяти в управляющее устройство с помощью считывающего устройства поступает информация а. Если на шаге tуправляющее устройство М. находится в состоянии g_i и программа М. содержит команду , то на следующем шаге t+i управляющее устройство будет находиться в состоянии q_j , а содержимое внешней памяти и положение считывающих устройств будет изменено согласно b. Обычно среди состояний управляющего устройства выделяются одно или несколько начальных и одно или несколько заключительных. Перед началом работы управляющее устройство приводится в начальное состояние, конец работы определяется заключительным состоянием.

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

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

1. Организация внешней памяти. Наибольшее распространение получило введение нескольких лент (многоленточные машины Тьюринга). Изучаются также М. с односторонними и многомерными лентами, с внешней памятью в виде бесконечного графа (напр., в виде бесконечного двоичного дерева). Другой подход состоит в замене традиционной ленты регистрами или счетчиками, способными содержать произвольные натуральные (целые) числа или слова произвольной длины. Так обстоит дело с машинами Шефердсона - Стургиса [6], машиной Минского [3] и машиной с произвольным доступом к памяти.

2. Хранение, преобразование и получение информации из внешней памяти. Рассматриваются М., у к-рых часть информации из внешней памяти, не поступающая в управляющее устройство в течение нек-рого времени, зависящего от входа, становится в дальнейшем вообще недоступной для читающих устройств М. На близкой идее основано определение машин Тьюринга с лентами магазинного типа (магазинные автоматы).

Для М., к-рые воспринимают и преобразуют информацию из внешней памяти побуквенно, типичным ограничением является запрет печатать одни символы вместо нек-рых других. Таковы, в частности, нестирающие машины Тьюринга и двусторонние автоматы, эквивалентные конечным автоматам. Сюда же относят важный класс абстрактных М.- конечные автоматы. Однако более распространенными являются ограничения на объем внешней памяти, время работы и т. п. Напр., линейно ограниченные автоматы представляют собой обычные машины Тьюринга, у к-рых длина используемой в вычислении ленты ограничена линейной функцией от длины входа.

Часто получение информации из внешней памяти происходит с помощью нескольких головок. Более общий подход состоит в том, что на внешней памяти М. определяются общерекурсивные предикаты. Набор значений этих предикатов представляет собой информацию, к-рая поступает в управляющее устройство М. Эта идея используется в машинах Шефердсона - Стур-гиса, у к-рых вдобавок запись информации во внешнюю память может осуществляться с помощью произвольных общерекурсивных функций.

3. Способ функционирования. Здесь различают детерминированные, недетерминированные и вероятностные М. У детерминированных М. каждый шаг работы однозначно определяется состоянием управляющего устройства и информацией из внешней памяти, полученной с помощью читающих устройств. Программа недетерминированной М. может содержать различные команды с одинаковыми левыми частями. Поэтому для недетерминированной М. при заданном входе рассматривают не одно, а множество всех вычислений, согласованных с программой. Вероятностная М. представляет собой М., к-рая либо снабжена датчиком случайных чисел, либо имеет программу, в к-рой переходы от одних команд к другим осуществляются с заданными вероятностями.

В недетерминированном случае обычно рассматривают вычисления предикатов. Если недетерминированная машина Мвычисляет предикат р(x₁, . . ., х _n ), то р(x₁, . . ., х _n )истинен тогда и только тогда, когда среди всех возможных вычислений машины М, начинающихся с конфигурации K₁(x₁, . . ., х _n )существует вычисление, содержащее заключительную конфигурацию.

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

Лита.:[1] Автоматы. Сб. статей под ред. К. Э. Шеннона и Дж. Маккарти, пер. с англ., М., 1956; [2] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [3] Минский М., Вычисления и автоматы, цер. с англ., М., 1971; [4] Проблемы математической логики. Сб. переводов, М., 1970; [5] Сложность вычислений и алгоритмов. Сб. переводов, М., 1974; [6] Shepherdson J. С, SturgisH. E., "J. Assoc. Comput. Machinery", 1963, v. 10, №2, p. 217 - 55.

С. С. Марченков.

[6] Shepherdson J. С, SturgisH. E., "J. Assoc. Comput. Machinery", 1963, v. 10, №2, p. 217 - 55.

С. С. Марченков.