Funzione calcolabile e riduzioni: come sono sicuro che funziona?

Messaggioda the-informatematica » 11/02/2020, 21:18

Buonasera. Ho la seguente domanda a cui non riesco a rispondere da giorni.
Ho questo problema P={M1,M2|L(M1)$nn$L(M2)$!=$vuoto}
Ho lo svolgimento che ho capito, quello che vorrei sapere io sono queste due cose:
La funzione calcolabile che mi trasforma dal linguagio empty a questo esercizio propone una copia di M=M1=M2 , e una macchina costruita a blocchi. Il blocco interno ha due macchine universali che ricevono la macchina M e a loro volta ogni macchina universale riceve un Guess di una stringa generata non deterministicamente. Il mio dubbio fondamentale è come capisco che: questa funzione calcolabile va bene per il mio Problema P? Cioè ci sono dei casi che ho visto in cui ad esempio una funzione calcolabile non va bene per il problema (non posso ridurre a Ld il problema dell'arresto). in questo caso f va bene ma vorrei avere uno strumento che me lo fa capire sempre se la mia f va bene in ogni caso cioè vorrei poter essere in grado di capire da solo se la mia f è veramente applicabile. Ho molto bisogno di capire, vi prego aiutatemi, grazie.
the-informatematica
Starting Member
Starting Member
 
Messaggio: 3 di 10
Iscritto il: 05/02/2020, 20:57

Re: Funzione calcolabile e riduzioni: come sono sicuro che funziona?

Messaggioda the-informatematica » 16/02/2020, 09:42

Ho capito che la f calcolabile deve essere semplice da poter essere considerata banale per la mia riduzione e quindi le operazioni di check hanno sempre successo ma continuo a non capire come una riduzione da un problema ad un altro possa essere corretta o no
the-informatematica
Starting Member
Starting Member
 
Messaggio: 4 di 10
Iscritto il: 05/02/2020, 20:57

Re: Funzione calcolabile e riduzioni: come sono sicuro che funziona?

Messaggioda the-informatematica » 17/02/2020, 20:39

Mi auto rispondo di nuovo non avendo purtroppo ricevuto risposte da chi è sicuramente più esperto di me. Ho provato a constatare che nella riduzione dal linguaggio della diagonalizzazione al linguaggio dell'arresto non dovrebbe essere possibile fare questa riduzione perché le istanze si della diagonalizzazione non sono pure istanze si del linguaggio dell'arresto a causa della macchina della diagonalizzazione che non ha modo di garantire l'arresto. Vorrei altri pareri.
the-informatematica
Starting Member
Starting Member
 
Messaggio: 5 di 10
Iscritto il: 05/02/2020, 20:57


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite