Математическая энциклопедия - машина

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

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

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

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

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

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

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

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