Ответ 1
(примечание - термины "разрешимость Тьюринга" и "совместное разрешение Тьюринга" - одно и то же. Однако "опознаваемые Тьюрингом" и "со-Тьюринг-распознаваемые" не совпадают, и это то, что я "Я решил покрыть в своем ответе: причина в том, что если язык разрешима, то его дополнение также должно быть разрешимым. То же самое относится и к распознаваемым языкам.)
Интуитивно, язык Turing-узнаваемый, если есть некоторая компьютерная программа, которая, учитывая строку на языке, может подтвердить, что строка действительно находится в пределах языка. Эта программа может зацикливаться бесконечно, если строка не указана в языке, но она всегда гарантирует, что в конечном итоге она будет принята, если вы дадите ей строку на языке.
Хотя верно, что язык является коуринг-узнаваемым, если он является дополнением к языку, распознаваемому Тьюрингом, это определение не проливает много света на то, что происходит. Интуитивно, если язык распознается совместно с Turing, это означает, что есть компьютерная программа, которая, учитывая строку, не указанную на этом языке, в конечном итоге подтвердит, что строка не указана на языке. Это может быть бесконечно, если строка действительно находится в пределах языка. Причина этого проста: если какая-то строка w не содержится внутри языка, распознаваемого со стороны Тьюринга, то эта строка w должна содержаться в дополнении к этому узнаваемому со стороны Тьюринга языку, который (по определению) должен быть узнаваемым Тьюрингом. Поскольку w находится в узнаваемом по Тьюрингу дополнении, должна быть какая-то программа, которая может подтвердить, что w действительно находится в дополнении. Таким образом, эта программа может подтвердить, что w не находится в оригинальном распознаваемом языком Turing.
Короче говоря, узнаваемость по Тьюрингу означает, что есть программа, которая может подтвердить, что строка w находится на языке, а co-Turing-распознаваемость означает, что есть программа, которая может подтвердить, что строка w не находится в язык.
Надеюсь, это поможет!