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