EXT non è RE

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

Comments

  • Mi intrometto nella discussione per una domanda molto simile.

    Si può usare un procedimento del genere per dimostrare che EXT è non-RE?
  • Vediamo, come pensi di fare?
  • 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.
  • Riesci prima a fare un esempio di una funzione non in EXT?
  • Pensavo ad una funzione totale che restituisce un output fisso con qualunque input, quindi una funzione in TOT, ma non sono sicuro vada bene
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    Pensavo ad una funzione totale che restituisce un output fisso con qualunque input, quindi una funzione in TOT, ma non sono sicuro vada bene

    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.
  • La funzione caratteristica di K per esempio è non estendibile? Forse però è troppo strano come esempio..
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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 è?
  • 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 :/
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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 SisbarraAntonio Sisbarra Posts: 44
    edited February 2017
    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.
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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.
  • 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.
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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

    Perché? E' proprio questo che devi dimostrare, non puoi prenderlo per buono senza giustificazione.
  • Pensavo che il fatto che K non è decidibile rende impossibile la verifica "se x appartiene a K" alla macchina.
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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')."
  • 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.
  • 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 SisbarraAntonio Sisbarra Posts: 44
    edited February 2017
    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.
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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?
  • Eh perché il numero di passi che impiega una macchina x nel calcolare x, con x non appartenente a K, è infinito
  • 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.
  • Mmm non so in questo caso cosa si potrebbe fare :/
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    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 SisbarraAntonio Sisbarra Posts: 44
    edited February 2017
    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.
  • MindFlyerMindFlyer Posts: 436
    edited February 2017
    Secondo me sì

    Perché?

  • 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
  • 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?
  • 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)
Sign In or Register to comment.