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.