Возможно ли это? Предположим, что мы решили, что {| M - это TM и | L (M) | = n} Хотите, чтобы сборщик принял решение {| M - это TM и | L (M) | = n-1} Если возможно, как?Определитель принимает решение {<M> | M является TM и | L (M) | = n}, построение решения принимает n-1
Чтобы увидеть, что мы можем решить | L (M) | = n - 1, предположим, что построим TM N для языка L (N) = L (M) U {a}, где a - символ не в алфавите языка L (M). N будет принимать точно строки, которые принимает M, плюс эту еще одну строку, которую M не удалось принять. Следовательно, N принимает n строк тогда и только тогда, когда M принимает n - 1 строк. Чтобы решить, | L (M) | = n - 1, то достаточно запустить наш определитель на N и посмотреть, будет ли | L (N) | = n.
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что речь идет о чистой теоретической CS, которая лучше подходит для cs.stackexchange.com. – templatetypedef