В теории вычислимости понятие универсаль ной в некотором классе вычислительных форма лизмов машины (программы) играет важную роль. Универсальная программа получает на вход код некоторой программы PR из рассматривае мого класса и входные данные для нее и вычисля ет результат работы программы PR на этих вход ных данных. В случае реактивных программ или автоматных устройств, когда важен не только ре зультат работы, но и поведение системы, от уни версальной программы естественно также требо вать симуляции поведения заданной программы. Наряду с универсальной машиной Тьюринга, ко торая, получая на вход код произвольной маши ны Тьюринга, моделирует ее работу, универсаль ные машины существуют и в некоторых ограни ченных классах машин, в частности для машин Тьюринга с некоторыми сложностными ограни чениями [8]. Однако для многих классов более уз ких, чем машины Тьюринга, вычислительных формализмов универсальные машины сами не принадлежат этому классу. В частности, в [7] до казано, что в классе конечных автоматов универ сального автомата не существует.
展开▼
