Как продемонстрировать, что множество разрешимо, полуразрешимо или не полуразрешимо?

Question

Меня попросили доказать, является ли следующий набор разрешимым, полуразрешимым или недостижимым:

Другими словами, это набор входов, такой, что существует машина Тьюринга, закодированная натуральным y с входом p, который возвращает свой ввод.

Рассмотрим множество K как множество натуральных чисел, так что машина Тьюринга, закодированная с помощью x и вход x, останавливается. Это демонстрируется как неразрешимый набор.

Я думаю, что мне нужно найти уменьшение K до L, но я не знаю, как доказать, что L разрешима, полуразрешима или не полуразрешима.

Answer 1

L может не выглядеть разрешимым на первый взгляд, потому что в него включен этот мерзкий неограниченный квантификатор, который, по-видимому, делает необходимым бесконечный поиск, когда вы ищете a, удовлетворяющее условию для конкретного p.

Однако ответ намного проще: существует машина Тьюринга M, которая всегда возвращает свои входные данные, т. Е. M (p) = p выполняется для all p на рассматриваемом языке. Пусть y будет кодом M. Тогда вы можете использовать этот же y для всех p, показывая, что L содержит всех слов языка. Следовательно, L, конечно, разрешимо.

Фактически, это пример, демонстрирующий принцип экстенсиональности (если два набора имеют одинаковые элементы, а один разрешим, то другой тоже разрешим, даже если он не выглядит так ).