Задание

В информатике существуют алгоритмически неразрешимые задачи. Соотнесите пример задачи с проблемой неразрешимости задачи.

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

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

Проблема тотальности

Проблема распознования видимости

Проблема самоприменимости

Даны описание процедуры и её начальные входные данные. Требуется определить, завершится ли когда-либо выполнение процедуры с этими данными или зациклится.

По двум произвольным заданным алгоритмам P и Q определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.

По произвольно заданному алгоритму Р определить, будет ли он останавливаться на всех возможных наборах исходных данных.

Задача разработать алгоритм, позволяющий установить, можно ли вывести формулу Б из формулы А в рамках заданной системы аксиом.

По заданному тексту программы Р определить, останавливается ли программа Р, если ей на вход подать текст этой же программы.