В этом ответе предполагается, что L - это язык всех представлений машин Тьюринга, которые останавливаются при некотором вводе.
Во-первых, этот язык должен быть полуразрешимым или рекурсивно перечислимым, потому что мы можем перечислять кодировки машины Тьюринга, которые останавливаются при некотором вводе. Для этого начните перечислять все двоичные строки. На каждом этапе начинайте новую TM, которая начинает моделировать выполнение машины, закодированной только что сгенерированной строкой на всех возможных входах. Продолжайте так, чтобы все возможные кодировки TM моделировались на всех возможных входах. Ласточкин хвост для выполнения этих машин, чтобы каждая из них получала свой следующий квант времени в течение конечного времени, чтобы каждый возможный вход моделировался на каждой возможной ТМ в конечное время. Если какая-либо из симуляций когда-либо останавливается, то мы распечатываем кодировку, которая остановилась на входе, и мы можем прекратить симуляцию этой кодировки. Это должно в конечном итоге распечатать любую кодировку на языке, поэтому язык перечисляется. Это означает, что мы можем ответить на вопрос, "это ТМ на языке?" для любой предоставленной ТМ, учитывая, что ответ - да (поскольку мы в конечном итоге встретимся с ней)
Во-вторых, язык не может быть решаемым или рекурсивным, потому что это дает нам четкий метод решения проблемы остановки: спросите, есть ли рассматриваемый ТМ на языке, и получите ответ «да» или «нет» относительно того, является ли он останавливается на некотором входе. Мы всегда можем изменить интересующий ТМ так, чтобы он мог останавливаться только на том, что представляет интерес, и затем подавать его в наш решающий орган, если мы имеем в виду конкретный вклад.
В-третьих, эти факты подразумевают, что язык не является рекурсивно-перечислимым, поскольку его рекурсивно-перечислимый и ко-рекурсивно-перечислимый подразумевают, что он рекурсивный, а это не так.