Алгоритмически неразрешимые задачи. Задача останова.

Алгоритмически неразрешимые задачи. Задача останова.

Проблема самоприменимости
Теорема
Не существует алгоритма А, который для любого алгоритма Е по его записи мог бы определить, является ли Е самоприменимым или нет.

Проблема останова
Теорема
Не существует алгоритма, который бы по записи произвольного алгоритма Е и слову Р определял бы, является ли Е применимым к Р.

Проблема эквивалентности

Алгоритмы В и С эквивалентны в алфавите А(на множестве А*), если к каждому слову из А* они:
- либо одновременно неприменимы,
-либо одновременно применимы и выдают одинаковое выходное слово.

Проблема эквивалентности

Алгоритмы В и С эквивалентны в алфавите А(на множестве А*), если к каждому слову из А* они:
- либо одновременно неприменимы,
-либо одновременно применимы и выдают одинаковое выходное слово.
Теорема
Не существует алгоритма, который для заданных двух алгоритмов по их записи определяет, являются они эквивалентными(в заданном алфавите) или нет.