Пример языка, который не может быть принят никакой МТ

[SteelRend]

Здравствуйте. Корректно ли рассматривать МТ, принимающую (значит, заканчивающую свою работу в допускающей конфигурации для каждого слова языка) такой язык: "коды всех машин Тьюринга, имеющих только бесконечные вычисления"? Конкретнее, $L = \{Kod(M)\#w | M $ имеет только бесконечные вычисления над $w \}$ ($Kod(M)$ -- код (представление в виде слова в некотором алфавите) МТ $M$) Всякая МТ $A$, принимающая этот язык, отклоняет коды всех МТ, имеющих конечные вычисления над $w$ (неважно, все ли они отклоняющие или есть среди них допускающие вычисления, главное чтобы длина их была конечной), и принимает коды МТ, у которых все вычисления над $w$ бесконечны. $A$ моделирует вычисление над входом $w$ переданной МТ $M$. Если $A$, моделируя вычисления $M$ над $w$, обнаруживает переход в допускающую или отклоняющую конфигурацию (или вычисление $M$ внезапно обрывается -- для заданных состояния $p$ и символа $a$ нет возможных переходов, при этом $p$ не является конечным/финальным состоянием), то она отклоняет свой вход. Чтобы принимать МТ с только лишь бесконечными вычислениями, МТ $A$ должна "уметь" определять бесконечность моделируемого ею вычисления. Как мне кажется, это невозможно выполнять алгоритмически (иначе проблема останова была бы решаемой для всех возможных входов), поэтому этот язык действительно не принимается никакой МТ.

[mihaild]

Что такое "вычисления над $w$" и "имеющие только бесконечные вычисления" - "не останавливающиеся ни на каком входе"? Такой язык действительно неразрешим (но коперечислим), правда для доказательства сводить к нему проблему останова (или что-то аналогичное) нужно более явно.
(либо можно воспользоваться теоремой Райса)

[SteelRend]

mihaild в сообщении #1323048 писал(а):

Что такое "вычисления над $w$"

Вычисление над $w$ -- последовательность конфигураций $C_0, C_1, ..., C_i, ...$, где $C_0$ -- начальная конфигурация над $w$ (МТ находится в состоянии $q_0$ и на её ленте записано слово $w$) и выполнено $C_i \vdash C_{i+1}$ (т.е. МТ непосредственно переходит из $C_i$ в $C_{i+1}$).

Цитата:

"имеющие только бесконечные вычисления"

Если рассматривается ДМТ, то у неё есть только одно возможное вычисление над $w$, и его бесконечность означает, что последовательность $C_0, C_1, ..., C_i, ...$ -- бесконечная. Если говорим о НМТ, то это значит, что все ветви в её дереве конфигураций/вычислений бесконечны.

Цитата:

"не останавливающиеся ни на каком входе"

Можно это интерпретировать и так, но даже если на каких-то входах МТ будут останавливаться, то это ничего не изменит, учитывая то, как я определил язык $L$ (в кавычках немного неточное описание).

[mihaild]

SteelRend в сообщении #1323050 писал(а):

Вычисление над $w$

Слегка непривычная терминология (это обычно называется "протокол на входе $w$"). Но неважно.

SteelRend в сообщении #1323050 писал(а):

в кавычках немного неточное описание

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

Дополнение $L$, как вы указали, перечислимо - и если бы $L$ был перечислим, то он был бы разрешим. А к нему сводится проблема останова (она им и задается).

SteelRend в сообщении #1323043 писал(а):

заканчивающую свою работу в допускающей конфигурации для каждого слова языка

По-хорошему, нужно явно сказать, что происходит на словах не из языка - под ваше определение формально подходит и принимающая все слова МТ.

В целом рассуждения у вас правильные, только аккуратности слегка не хватает.