Czy możemy pokazać, że języka nie da się wyliczyć, pokazując, że nie ma dla niego weryfikatora?

Jedna z definicji zestawu wyliczalnego (ce, równoważnego rekurencyjnie wyliczalnemu, równoważnego semidecidable) jest następująca:

$A \subseteq \Sigma^*$ oznacza, że ​​istnieje rozstrzygalny język$V\subseteq \Sigma^*$ (zwany weryfikatorem) st dla wszystkich$x\in \Sigma^*$ ,

IFF istnieje y ∈ Ď * st ⟨ x , y ⟩ ∈ V .$x\in A$$y\in\Sigma^*$$\langle x, y \rangle \in V$

Jednym ze sposobów wykazania, że ​​dany język nie jest ce, jest wykazanie, że nie ma dla niego żadnego weryfikowalnego weryfikatora Czy ta metoda jest przydatna do wykazania, że ​​języki nie są w praktyce?$V$

W praktyce zwykle nie udowadniamy, że język jest ponownie lub nie. Jeśli język jest ponownie, chcemy wiedzieć, czy jest on rekurencyjny. Jeśli tak nie jest, chcemy wiedzieć, jaki ma on stopień Turinga, a nie tylko, że stopień Turinga nie jest re.

Na przykład, jeśli jest problemem z P ′ ≡ T 0 $P$$P' \equiv_T 0'''$ następnie nie jest ponownie, ale o fakt, że skok Turing jest bardziej pouczające niż tylko znając P nie jest ponownie$P$$P$

Tak więc, chociaż w zasadzie można wykazać, że język nie jest poprawny, udowadniając, że nie ma weryfikatora, w praktyce bardziej pouczające jest udowodnienie, że język nie jest poprawny, pokazując, że oblicza coś, czego żaden zestaw nie może obliczyć; charakter tego „czegoś” zazwyczaj dostarcza użytecznych informacji na temat badanego problemu.

Aby wyjaśnić terminologię, używam jasnego: decidable = recursive = computable, semidecidable = recursively enumerable = computable enumerable, co-semidecidable = co-recursively enumerable = co-computable enumerable.

W praktyce powszechną metodą wykazania, że ​​język nie jest rozstrzygalny, jest wykazanie, że nie można go rozstrzygać i że jest on rozstrzygalny. Następnie korzystasz z faktu, że każdy język, który jest zarówno półdecydowalny, jak i pół-półdecydowalny, również jest rozstrzygalny, aby stwierdzić, że Twój język nie jest półdecydowalny. (zwróć uwagę, że działa to tylko w jednym kierunku: język nie może być ani w połowie, ani w połowie, w którym to przypadku potrzebujesz innej metody)

Jako przykład: wiemy, że decydowanie o tym, czy jest niejednoznaczne, jest nierozstrzygalne, ale łatwo jest współdecydować: po prostu podajesz ciąg, który ma dwie różne analizy. Oznacza to, że nie jest rozstrzygalne, czy C F G jest niejednoznaczny.$\mathrm{CFG}$$\mathrm{CFG}$

Inną metodą jest wykazanie, że język jest kompletny dla pewnego wyższego poziomu hierarchii arytmetycznej .

Oczywiście można bezpośrednio udowodnić, że nie ma weryfikatora, ale jest to często żmudne, ponieważ zwykle powtarza dowód, że problem zatrzymania jest nierozstrzygalny. Zauważ jednak, że powyższy argument zasadniczo niejawnie dowodzi, że nie może istnieć żaden weryfikator, więc sądzę, że możesz powiedzieć, że jest to metoda udowodnienia, że ​​nie ma weryfikatora, ale wtedy możesz rozważyć każdy dowód braku rozstrzygalności jako dowód, że istnieje nie verfier.