ВЫЧИСЛЕНИЯ В РЕАЛЬНОЕ ВРЕМЯ
на автоматах — вычисления, при которых автомат вырабатывает результат за время, необходимое для подачи на него значения аргумента. Примером таких вычислений могут служить вычисления на автоматах конечных. Формальное описание В. в р. в. удобнее всего дать в терминах вычисления операторов (см. Поведение автоматов). Пусть оператор О отображает мн-во бесконечных последовательностей во входном алфавите X во мн-во бесконечных последовательностей в выходном алфавите У. Говорят, что автомат

вычисляет в реальное время оператор О, если

на

-ом такте

получая на вход

выдает на выход

, где

есть результат применения О к
Класс операторов, вычислимых в реальное время, не исчерпывается конечно-автоматными операторами. Примером не конечно-автоматного оператора, который вычислим на многоленточной Тьюринга машине в реальное время, является оператор распознавания симметрии. Он отображает произвольную двоичную последовательность
в такую двоичную последовательность
что
тогда и только тогда, когда
- симметричное слово (т. е.
для всех
Известно, что оператор распознавания симметрии не вычислим в реальное время на одноленточных машинах Тьюринга. Примером не конечно-автоматного оператора, вычислимого в реальное время на автоматах итеративных, является оператор умножения, отображающий каждую пару последовательностей
в последовательность
где
— первые
разрядов произведения чисел
В теории В. в р. в. наибольший интерес представляет изучение классов операторов, вычислимых в реальное время на автоматах того или иного типа. Операторы, вычислимые в реальное время при любой известной концепции автомата, являются вычислимыми операторами без предвосхищения. Обратное неверно. Более того, для многих достаточно широких классов автоматов класс операторов, вычислимых в реальное время, является довольно узким и не содержит многих естественно определяемых операторов.
Приведем некоторые результаты сравнения (по типу вычисляющих автоматов) классов операторов, вычислимых в реальное время: 1) существует оператор, вычислимый в реальное время на двухленточной машине Тьюринга и не вычислимый в реальное время ни на какой одноленточной машине Тьюринга; 2) для любого
существует оператор, вычислимый в реальное время на
-мерном итеративном автомате и не вычислимый в реальное время ни на каком
итеративном автомате; 3) классы операторов, вычислимых в реальное время на многоголовочных машинах Тьюринга и на многоленточных машинах Тьюринга, совпадают. Результаты 1) —3) естественно переинтерпретируются в терминах вычисления предикатов. Важную интерпретацию в терминах порождения последовательностей допускают операторы с унарным входным алфавитом
. Говорят, что бесконечная последовательность Р порождается в реальное время автоматом
, если оператор, отображающий последовательность
в
, вычислим в реальное время на
. Пусть сверх того Р — двоичная последовательность, содержащая бесконечное число символов 1.
связывается монотонно возрастающая ф-ция
такая, что
тогда и только тогда, когда
есть
-ое вхождение символа 1 в
. В этом случае говорят, что функция
вычислима в реальное время на
. Другими словами, рассматривают автомат автономный
, выдающий (двоичную) последовательность и
принимают равным номеру такта, в котором вырабатывается
-ая единица. Напр., с
связывается ф-ция
которая вычислима в реальное время на одноленточной машине Тьюринга. Приведем осн. результаты, связанные с порождением последовательностей и вычислением ф-ций в реальное время: (1) для всякого
существует последовательность, порождаемая в реальное время машиной Минского с к
лентами, и не порождаемая в реальное время никакой машиной Минского с к лентами; (2) существует последовательность, порождаемая в реальное время одноленточной машиной Тьюринга, и не порождаемая в реальное время никакой машиной Минского; (3) класс функций, вычислимых в реальное время на машинах Мипского, содержит всевозможные полиномы, степенные функции
постоянная),
и замкнут относительно операций сложения, умножения, суперпозиции, возведения в степень; (4) класс ф-ций, вычислимых в реальное время на машинах Тьюринга, содержит не примитивно-рекурсивные функции и замкнут относительно операций, перечисленных в (3); (5) существует монотонно-возрастающая примитивно-рекурсивная ф-ция, не вычислимая в реальное время на машинах Тьюринга.
Лит.: Фрейвалд Р. Сложность распознавания симметрии на машинах Тьюринга с входом. «Алгебра и логика. Семинар», 1965, т. 4, в. 1; Барздинь Я. М. Емкость среды и поведение автоматов. «Доклады АН СССР», 1965, т. 160, № 2; Фишер П. Многоленточные и бесконечные автоматы. В кн.: Кибернетический сборник. Новая серия, в. 5. М., 1968; Слисенко А. О. Распознавание предиката симметрии многоголовчатыми машинами Тьюринга со входом. «Труды Математического института им. В. А. Стеклова АН СССР», 1973, т. 129; F ischcr Р. С., Meyer A. R., Rosenberg A. L. Time-restricted sequence generation. «Journal of the computer and system sciences», 1970, v. 4, № 1.
М. К. Валиев, В. А. Непомнящий.