Обратите внимание, что подавляющее большинство проблем соответствует критерию, который вы ищете: и проблема, и ее дополнение не являются полуразрешимыми. Это связано с тем, что существует только счетное количество полуразрешимых проблем, но существует бесчисленное множество проблем.
Для примера, пусть будет проблемой остановки для машин Тьюринга и пусть М класса машин Тьюринга с оракулом для H . Пусть H 2 будет проблема остановки для M . Я утверждаю, что ни H 2, ни ¯ H 2 не являются полуразрешимымиHMHH2MH2H2¯¯¯¯¯¯
Мы можем показать, что не определяется ни одной машиной из M : аргумент совпадает с аргументом о том, что проблема остановки обычной машины Тьюринга H не решается ни одной обычной машиной Тьюринга. Теперь предположим, что для противного , что H 2 является полу-решению какой - то обычной машины Тьюринга T . Что ж, с оракулом для H мы можем проверить, останавливается ли T для какого-либо конкретного ввода, что противоречит тому факту, что ни одна машина в M не принимает решение H 2 . Итак, H 2H2MHH2THTMH2H2 не является полуразрешимым.
Остается показать , что не пол-разрешим. Во-первых, обратите внимание, что он полуопределен машиной в M : опять же, аргумент такой же, как H , полуопределенный обычной машиной Тьюринга. ¯ H - не может быть пол-решению какой - то машина в M , потому что, если он был, H 2 и ¯ H 2 будут как бы пол-решения машин M , поэтому оба языка будет решаться на машинах в M . Но мы уже знаем , что H 2 не решается на любой машине в M . Следовательно,H2¯¯¯¯¯¯MHH2¯¯¯¯¯¯MH2H2¯¯¯¯¯¯MMH2M не полу решил на любой машине в M. Кроме того, ¯ Н 2 не является полу-решению любой обычной машины Тьюринга, такМ содержит каждую обычную машину Тьюринга. (Обычная машина Тьюринга - это машина Тьюринга с оракулом для Н,которая никогда не использует этот оракул.)H2¯¯¯¯¯¯MH2¯¯¯¯¯¯MH