Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)

Это же вроде известно. Язык, строками которого являются пары (m,n), где m — строковое представление МТ, а n — строковое представление набора данных, является рекурсивно-перечислимым (но, разумеется, не рекурсивным). Это язык универсальной МТ. Комплементарный ему язык — не является. Принимая первое утверждение за факт, второе доказывается довольно просто: если комплементарный язык является рекурсивно-перечислимым, то возьмем две МТ: первая будет рекурсивно выписывать все слова первого языка, а вторая — второго. В результате для любого набора данных конкретной МТ можно будет за конечное время проверить, какая МТ его сгенерировала, что являлось бы решением проблемы останова.

Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Доказать/опровергнуть разрешимость обратной проблемы останова (построить МТ, которая по заданной МТ генерирует все наборы данных, на которых та останавливается)

Это же вроде известно. Язык, строками которого являются пары (m,n), где m — строковое представление МТ, а n — строковое представление набора данных, m останавливается на n, является рекурсивно-перечислимым (но, разумеется, не рекурсивным). Это язык универсальной МТ. Комплементарный ему язык — не является. Принимая первое утверждение за факт, второе доказывается довольно просто: если комплементарный язык является рекурсивно-перечислимым, то возьмем две МТ: первая будет рекурсивно выписывать все слова первого языка, а вторая — второго. В результате для любого набора данных конкретной МТ можно будет за конечное время проверить, какая МТ его сгенерировала, что являлось бы решением проблемы останова.