EXT non è RE

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

This discussion was created from comments split from: Riduzione di K complemento a TOT.

Antonio Sisbarra
Si può usare un procedimento del genere per dimostrare che EXT è non-RE?

MindFlyer
Vediamo, come pensi di fare?

Antonio Sisbarra
Allora, se ho capito bene EXT è l'insieme degli indici delle funzioni estendibili a funzione calcolabile totale, per esempio la funzione f(x) che restituisce sempre x, se x è diverso da 0, altrimenti indefinita.
Pensavo di ridurre K negato a EXT, facendo vedere che se x appartiene a K, f(x) non appartiene a EXT e che se x non appartiene a K, f(x) appartiene a EXT.
Per fare ciò stavo pensando di definirmi la classica funzione parziale, però a questo punto mi sono bloccato.

MindFlyer
Riesci prima a fare un esempio di una funzione non in EXT?

Antonio Sisbarra
Pensavo ad una funzione totale che restituisce un output fisso con qualunque input, quindi una funzione in TOT, ma non sono sicuro vada bene

MindFlyer
Ovviamente no... Se è già totale, è banalmente estendibile a funzione totale (non bisogna aggiungere nulla per estenderla). Ci vuole una funzione calcolabile che non sia definita su qualche input, e che comunque la si definisca (o "estenda") su tutti quegli input si ottiene una funzione non più calcolabile.

Una volta trovata una funzione non in EXT, si può rifare più o meno una riduzione nello stile di quella per TOT.

Antonio Sisbarra
La funzione caratteristica di K per esempio è non estendibile? Forse però è troppo strano come esempio..

MindFlyer
La funzione caratteristica di K è una funzione totale e non calcolabile. Quindi non è un buon esempio per questi due motivi.

Se invece prendi la funzione che fa 1 su K ed è indefinita altrove (cioè la funzione semicaratteristica di K), questa è calcolabile e non totale, ma purtroppo è estendibile alla funzione costantemente 1, che è calcolabile e totale. Quindi anche la semicaratteristica di K è in EXT.

Però questa idea va nella direzione giusta. Finché ti limiti a funzioni che semidecidono insiemi, non vai da nessuna parte, perché tutte queste si estendono alla costante 1. Però puoi trasformare un po' l'output di queste funzioni semicaratteristiche e calcolare qualcosa che dia più informazioni. Per esempio, se x è in K, puoi restituire non semplicemente 1, ma il numero di passi che la macchina x-esima fa su input x prima di terminare (se x non è in K, la funzione è indefinita come al solito). Questa funzione è calcolabile, e ti preannuncio che non è in EXT. Perché non lo è?

Antonio Sisbarra
Secondo me non è in EXT perché non si sa a priori quanti passi fa una macchina su un input, a meno di andare a eseguire la macchina. Però se vado a eseguire la macchina mi scontro col problema della fermata quindi non posso dire a priori che è totale.
Almeno così sto ragionando io :/

MindFlyer
Intuitivamente è così, ma non si può essere sicuri che sia un ragionamento giusto finché non lo si formalizza.

Diciamo che abbiamo quella funzione calcolabile che ho definito sopra; chiamiamola f. Estendiamo f arbitrariamente su tutti gli input in cui è indefinita, ottenendo f'. Adesso devi dimostrare che se f' è calcolabile, allora riesci a decidere K. Come fai?

Antonio Sisbarra
Allora, la macchina M che calcola f' dovrebbe andare in uno stato di terminazione in tutti i casi per essere totale.
Questa M simula Mx(x) calcolando man mano i passi in un contatore.
Per assurdo M deve essere totale quindi terminare sempre.
Però Mx se non appartiene a K non terminerà mai applicato a x, e quindi M se fosse in grado di terminare sempre vorrebbe dire che sono in grado di decidere se una M appartiene a K oppure no.

MindFlyer
No, stai facendo le cose al contrario. Penso che il problema di fondo sia che confondi funzioni e algoritmi.

Mi stai facendo vedere che un "candidato algoritmo" M scelto da te per calcolare f' non è in realtà un algoritmo che calcola f'. Sarebbe come dire che siccome il MergeSort non è un algoritmo che calcola numeri primi, allora i numeri primi non sono calcolabili. Non stai in effetti dicendo ancora niente su tutti gli altri possibili algoritmi che non sono M e che potrebbero calcolare f', e quindi non hai detto nulla sulla non calcolabilità di f'.

Devi assumere di avere un qualche algoritmo M (che non conosci) per calcolare f'. Poi devi prendere un numero x e farmi vedere come puoi decidere se x è in K o meno usando M (come una "scatola nera" che calcola f'). Se riesci a fare questa cosa, puoi concludere che siccome K non è decidibile, allora l'esistenza di M è assurda, e quindi f' non è calcolabile.

Antonio Sisbarra
Quindi assumo che esista un M qualsiasi che calcoli f'.
Preso un numero x M mi restituisce i passi di computazione effettuati se x appartiene a K, 0 se non appartiene a K (devo estendere la funzione "passi calcolati" a tutti gli indici possibili e non solo quelli di K).
Visto che K non è decidibile M non può esistere e quindi f' non è calcolabile.

MindFlyer
0 se non appartiene a K
No, non necessariamente 0. EXT non è l'insieme degli indici delle funzioni calcolabili parziali estendibili a funzioni calcolabili totali aggiungendo 0 dove sono indefinite. Le si può estendere con qualunque numero, anche non 0. Infatti sopra ho definito f' come una funzione che estende "arbitrariamente" f, nel senso che mette valori qualsiasi dove f non è definita.
Visto che K non è decidibile M non può esistere e quindi f' non è calcolabile.
Perché? E' proprio questo che devi dimostrare, non puoi prenderlo per buono senza giustificazione.

Antonio Sisbarra
Pensavo che il fatto che K non è decidibile rende impossibile la verifica "se x appartiene a K" alla macchina.

MindFlyer
Appunto, come dicevo sopra, non bisogna confondere funzioni con algoritmi. f' è una funzione, mentre l'algoritmo che dice "se x appartiene a K" è solo uno degli infiniti possibili algoritmi che potrebbero calcolare f'.

Segui la traccia che ti ho dato sopra:
"Poi devi prendere un numero x e farmi vedere come puoi decidere se x è in K o meno usando M (come una "scatola nera" che calcola f')."

Antonio Sisbarra
Ho sbagliato, volevo scrivere "se x non appartiene a K".
Il problema secondo me è che un qualsiasi algoritmo non può stabilire la non appartenenza di un elemento all'insieme K.
Anche perché dovrebbe utilizzare un numero limitato di passi e quindi si crea il problema della fermata.

MindFlyer
un qualsiasi algoritmo non può stabilire la non appartenenza di un elemento all'insieme K.
Su questo siamo tutti d'accordo, perché la non decidibilità di K non è mai stata in discussione. Ma torno a dire, perché mai un algoritmo che calcola f' deve per forza stabilire se un elemento appartiene a K? Torno anche a dire che le funzioni non sono algoritmi, sono solo coppie di numeri.

Antonio Sisbarra
Ma perché f' per definizione deve restituire come risultato (nel caso in cui x appartenga a K) il numero di passi che fa la macchina x-esima su x.
In caso contrario deve restituire un qualsiasi numero come hai detto tu prima.
Perciò l'algoritmo che calcola f' deve per forza distinguere i casi di appartiene/non appartiene a K.

MindFlyer
No. Quello è solo il modo in cui l'ho "costruita" per definirla. Nessuno dice che debba essere per forza l'unico modo esistente di calcolarla.

Ripensa all'esempio di prima: prendiamo la funzione f semicaratteristica di K. Questa è 1 su K e indefinita fuori da K. La estendo a f' dicendo che se x è in K, f' continua a fare 1. Se x invece non è in K, f' fa 1. Il risultato è la funzione costantemente 1, ma non è vero che per calcolare questa f' devo per forza decidere se x è in K. Per calcolarla, basta restiture 1 senza fare niente.

Tornando al nostro caso, potrebbe esistere un algoritmo che fa cose stranissime e che non c'entrano niente con K, e "per culo" calcola proprio la nostra f'. Perché questo non è possibile?

Antonio Sisbarra
Eh perché il numero di passi che impiega una macchina x nel calcolare x, con x non appartenente a K, è infinito

MindFlyer
Ripeto: non è detto che per calcolare f' si debba per forza simulare la macchina x su x e contarne i passi. Questo è solo il modo in cui ho definito f', ma potrebbe non essere l'unico modo di calcolarla. Pensa all'esempio che ho fatto un momento fa sulla semicaratteristica di K.

Antonio Sisbarra
Mmm non so in questo caso cosa si potrebbe fare :/

MindFlyer
Ok, abbiamo una macchina M che "per magia" calcola f'. Adesso prendiamo un x, e chiediamoci se è in K. Per deciderlo, possiamo usare M. Allora simuliamo M su x, questa termina perché f' è totale, e restituisce un numero t. Sappiamo che se x è in K, t è certamente il numero di passi che la macchina x fa su input x prima di terminare (perché così è definita f'). Altrimenti, t è un numero qualunque che sicuramente non è il numero di passi che la macchina x fa su input x prima di terminare, anche perché non termina. Dunque, avendo t, possiamo stabilire se x è in K o non lo è?

Antonio Sisbarra
Secondo me sì e questo però sarebbe un assurdo perché K non è decidibile.
Non avevo pensato al fatto che M poteva essere usata in questa maniera.

MindFlyer
Secondo me sì
Perché?

Antonio Sisbarra
Verificando questo numero t con una nuova computazione di M su x e vedendo se i passi sono davvero t?
Però secondo me c'è una via più semplice

MindFlyer
No, lo verifichi con la computazione della macchina x su input x (forse era questo che volevi dire).

Ricapitolando:
ho un input x, calcolo f'(x), poi simulo la macchina di indice x su input x per f'(x) passi. Se la macchina termina, concludo che x è in K, altrimenti concludo che non è in K. Quindi poter calcolare f' rende K decidibile, assurdo.

Adesso che abbiamo trovato una funzione non in EXT, possiamo fare la riduzione dal complementare di K a EXT?

Antonio Sisbarra
Sisi intendevo quello.
Per la riduzione applico un procedimento simile a quello usato per ridurre a TOT.
Solo che quando x appartiene a K restituisco 1(funzione estendibile a TOT essendo già totale)
Se x non appartiene a K restituisco la f' appena calcolata (finalmente)

MindFlyer
No, per due motivi.

Primo, la riduzione non dev'essere da K a EXT, ma dev'essere dal complementare di K a EXT.

Secondo, non puoi verificare se x non appartiene a K (altrimenti decideresti K). Puoi solo ciclare all'infinito cercando di farlo. Quindi non puoi semplicemente dire "restituisco f'". Devi fare qualcosa che generi in qualche modo f' o qualcosa di abbastanza similie "strada facendo".

Antonio Sisbarra
Hai ragione, l'ora non mi aiuta. Ci penserò grazie mille comunque!!
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”