ВЫЧИСЛЕНИЯ В РЕАЛЬНОЕ ВРЕМЯ

на автоматах — вычисления, при которых автомат вырабатывает результат за время, необходимое для подачи на него значения аргумента. Примером таких вычислений могут служить вычисления на автоматах конечных. Формальное описание В. в р. в. удобнее всего дать в терминах вычисления операторов (см. Поведение автоматов). Пусть оператор О отображает мн-во бесконечных последовательностей во входном алфавите 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.

М. К. Валиев, В. А. Непомнящий.