- Универсальный исполнитель — это исполнитель, который может моделировать работу любого другого исполнителя.
- Любой алгоритм может быть представлен как программа для универсального исполнителя.
- Машина Тьюринга — это абстрактная машина, которая состоит из управляющего устройства, бесконечной ленты и устройства обращения к ленте.
- Универсальные исполнители (эквивалентны друг другу):
- машина Тьюринга;
- машина Поста (в отличие от машины Тьюринга работает с бинарным алфавитом);
- нормальные алгоритмы Маркова (подстановки строк).
- Универсальный исполнитель можно использовать для доказательства разрешимости или неразрешимости задач. Если доказано, что требуемый алгоритм не существует для универсального исполнителя, то задача неразрешима в принципе.
