Пусть А — инициальный 
автомат, в котором выделено заключительное состояние 
. В отличие от абстрактной теории автоматов, где алфавиты X и Y рассматриваются как абстрактные мн-ва, в Д. п. т. элементам этих алфавитов приписывается некоторый смысл (интерпретация). Для этого зафиксируем бесконечное мн-во В. Элементы 
мн-ва наз. информационными объектами, а само мн-во — информационный множеством. Полагаем, что в В выделено некоторое подмн-во 
начальных информационных объектов. Каждому выходному сигналу 
автомата А поставим в соответствие (частичное) преобразование 
мн-ва В в себя, а некоторым элементам b мн-ва В поставим в соответствие выходной сигнал 
автомата А. Если задано такое соответствие между выходными сигналами автомата А и преобразованиями мн-ва В, а также между элементами мн-ва В и входными сигналами автомата А, то говорят, что задана интерпретация входных и выходных сигналов автомата А. Инициальный автомат Мили с заключительным состоянием наз. дискретным преобразователем, если для его входных и выходных сигналов задана интерпретация. При этом гонорят, что дискретный преобразователь действует на мн-ве В, а преобразования 
элементарными операторами дискретного преобразователя. Информационное мн-во рассматривают как У-Х-автомат Мура (см. Мура автомат) с выделенным мн-вом 
начальных состояний, если ф-цию переходов определить равенством 
и взять 
в качестве ф-ции выходов. Полученный таким образом автомат В наз. автоматом операционным, а дискретный преобразователь при таком рассмотрении — автоматом управляющим.
Каждый дискретный преобразователь А определяет некоторое частичное преобразование 
мн-ва В состояний операционного автомата (информационного мн-ва). Это преобразование наз. оператором, представленным дискретным преобразователем А. Для того, чтобы вычислить 
следует операционный автомат установить в состояние b и соединить его с дискретным преобразователем А, установленным в начальное состояние. Получится система из двух автоматов (Илл. см. в ст. Автомат управляющий), которая начнет функционировать. Если через конечное число тактов автомат А перейдет в заключительное состояние а, то 
считается определенным и равным состоянию автомата В, в которое он перейдет в этот момент времени. В противном случае 
считается неопределенным. Говорят также, что А применим (не применим) к состоянию b автомата В. Очевидно, 
определенно тогда и только тогда, когда существуют слова 
и 
такие, что
где 
ограничение автоматного отображения 
представленного автоматом А на мн-во таких слов р, что 
Если слова, удовлетворяющие системе ур-ний (1) существуют, то они определены единственным образом и 
.
В качестве примеров дискретных преобразователей рассматривают головки Тьюринга машин, интерпретированные алгоритмов граф-схемы, логические операторные схемы алгоритмов, схемы алгоритмов над памятью, программы, микропрограммы и устройства управления ЦВМ. Исследована структура операционных автоматов, наиболее часто встречающихся в современных вычисл. машинах (см. Автомат регистровый). Одной из осн. задач Д. п. т. является изучение структуры преобразований, которые они представляют. Для этой цели был построен класс спец. алгебр (см. Алгебра алгоритмов). Исследование соотношений в конкретных алгебрах этого класса и преобразование выражений, соответствующих операторам, представляемым дискретными преобразователями, позволяет решать задачу синтеза дискретных преобразователей, удовлетворяющих тем или иным критериям оптимальности. Большое значение Имеет также изучение различных видов эквивалентности дискретных преобразователей.
Лит.; Глушков В. М. Теория автоматов и вопросы проектирования структур цифровых машин. «Кибернетика», 1965. JsTs 1; Глушков В. М., Летиневский А. А. Теория дискретных преобразователей. В кн.: Избранные вопросы алгебры и логики; Новосибирск. 1973.
Летиневский А. А.
