I linguaggi in $\mathsf{coRE} \setminus \mathsf{R}$ hanno macchine di Turing?

Question

Cosa possiamo dire delle lingue in $\mathsf{coRE} \setminus \mathsf{R}$?Esistono macchine di Turing per queste lingue?

So che $\overline{HP} \in \mathsf{coRE}$ non ha una macchina di Turing, e anche che sono presenti tutte le lingue in cui sono presenti le macchine di Turing $\mathsf{RE}$, quindi è vero che per qualsiasi lingua in $\mathsf{coRE} \setminus \mathsf{R}$ non c'è una macchina di Turing?Mi chiedo perché è così, qualcuno può approfondire?

Answer 1

Possiamo associare un linguaggio ad una macchina di Turing in diversi modi.

Se la macchina di Turing si ferma su tutti gli input, allora il linguaggio accettato dalla macchina di Turing è costituito da tutte le parole che causano l'arresto della macchina di Turing in uno stato di accettazione.La classe $\matematica{R}$ consiste di tutte le lingue accettate da alcune macchine di Turing.

Per una macchina di Turing arbitraria, il linguaggio riconosciuto dalla macchina di Turing è costituito da tutte le parole che causano l'arresto della macchina di Turing (in qualsiasi stato).La classe $\mathsf{RE}$ consiste di tutte le lingue riconosciute da qualche macchina di Turing.

Se $L \in \mathsf{coRE} \setminus \mathsf{R}$, quindi in particolare $L otin \mathsf{R}$, e quindi nessuna macchina di Turing accetta $L$.Se $L$ furono allora riconosciuti da qualche macchina di Turing $L \in \mathsf{RE}$.Tuttavia, da allora questo è impossibile $L \in \mathsf{RE} \cap \mathsf{coRE} = \mathsf{R}$.

Answer 2

Lasciatemi espandere la prima frase della risposta Yuval Filmus:

.

Possiamo associare una lingua a una macchina di Turing in diversi modi.

Yual menziona due: accettazione (che caratterizza $ \ mathsf {r} $ ) e riconoscimento ( che caratterizza $ \ mathsf {re} $ ). Ci sono altri, tuttavia. Ovviamente, potremmo prendere in considerazione il "co-riconoscimento" - dire che una macchina di Turing $ m $ "co-riconosce" una lingua $ L $ Se le stringhe in $ l $ sono esattamente le stringhe su cui $ m $ non halt. Quindi, naturalmente, il co-riconoscimento caratterizza $ \ mathsf {core} $ .

Tuttavia, è un po 'innaturale. Molto più naturale secondo me è la nozione di Limit Computability . Fraseti in termini di numeri naturali per semplicità, questo è il seguente:

.

Una funzione $ f: \ mathbb {n} \ reapyarrow \ mathbb {n} $ è limite computabile IF c'è un calcolo funzione $ h: \ mathbb {n} ^ 2 \ reapyarrow \ mathbbb {n} $ tale che $$ f (x )=LIM_ {S \ RightArdarrow \ Infty} h (x, s), $$ o più precisamente tale che per tutte le $ x $ c'è Qualche classe $ N $ tale che per tutti $ s> n $ Abbiamo $ h (x, s)= f (x) $ .

A Set $ x $ è limite computabile, nel frattempo, IF è una funzione calcolabile limitabile $ f $ in modo tale che $ x={i: f (i)= 1 \} $ . (Ci sono molte altre formulazioni equivalenti di questo.)

Si scopre che il limite del limite ha una caratterizzazione alternativa molto bella:

.

(shoenfield) una funzione $ f $ è limitabile Computable IF è calcolato relativo a il problema di halit $ \ vuoto '$ .

(e via Post Abbiamo un'altra caratterizzazione in termini di "complessità definitiva. ")

Ovviamente questo include sia $ \ mathsf {re} $ e $ \ mathsf {core} $ , e molto altro inoltre: ci sono set computabili relativi al problema di fermezza che non si tengono equivalenti a qualsiasi set in $ \ mathsf {re} $ . (Questo è difficile da provare!)

e ci sono ancora più modi per assegnare lingue per impostare; Ad esempio, possiamo parlare di "riconoscibilità del limite" (che è quella di limitare la calcurabilità in quanto la riconoscibilità è di accettazione), che ci dà il $ \ sigma ^ 0_2 $ lingue.