Esistenza problemi indecidibili
Salve a tutti!
Per un esame universitario di crittografia, devo studiare alcune nozioni di calcolabilità e complessità.
Nel libro di testo consigliato manca la parte relativa all'esistenza dei problemi indecidibili, di cui sono riuscito a procurarmi solo i lucidi delle lezioni.
Il problema è che questi lucidi sono molto succinti e quindi ho un pò di confusione in testa.
In particolare il mio problema è:
sui lucidi comincia a parlare dell'esistenza dei problemi decidibili e indecidibili, e fin qui tutto ok...poi c'è scritto che è stata dimostrata l'esistenza dei problemi indecidibili ma per arrivare a ciò ci sono prima alcune slide sugli insiemi numerabili e non numerabili, poi si passa al fatto che l'insieme dei problemi computazionali non è numerabile, subito dopo comincia la dimostrazione della non numerabilità dell'insieme F (la diagonale di Cantor), e poi passa al problema dell'arresto (con tesi di Church-Turing).
Premetto che presi singolarmente li ho capiti tutti questi concetti.
Chi sarebbe così gentile da spiegarmi qual'è il filo conduttore di tutto ciò, o ancora meglio indicarmi delle letture per chiarire questi concetti che ora mi appaiono sconnessi?
Per un esame universitario di crittografia, devo studiare alcune nozioni di calcolabilità e complessità.
Nel libro di testo consigliato manca la parte relativa all'esistenza dei problemi indecidibili, di cui sono riuscito a procurarmi solo i lucidi delle lezioni.
Il problema è che questi lucidi sono molto succinti e quindi ho un pò di confusione in testa.
In particolare il mio problema è:
sui lucidi comincia a parlare dell'esistenza dei problemi decidibili e indecidibili, e fin qui tutto ok...poi c'è scritto che è stata dimostrata l'esistenza dei problemi indecidibili ma per arrivare a ciò ci sono prima alcune slide sugli insiemi numerabili e non numerabili, poi si passa al fatto che l'insieme dei problemi computazionali non è numerabile, subito dopo comincia la dimostrazione della non numerabilità dell'insieme F (la diagonale di Cantor), e poi passa al problema dell'arresto (con tesi di Church-Turing).
Premetto che presi singolarmente li ho capiti tutti questi concetti.
Chi sarebbe così gentile da spiegarmi qual'è il filo conduttore di tutto ciò, o ancora meglio indicarmi delle letture per chiarire questi concetti che ora mi appaiono sconnessi?
Risposte
Non c'è proprio nessuno che può indirizzarmi sulla giusta strada? Anche solo ad indicarmi un testo da consultare?
Mi rispondo da solo.
Dopo tanto googlare, ho trovato un pdf che faceva al caso mio, non contiene tutte le spiegazioni rigorose, ma in compenso evidenzia bene i vari passaggi di quella dimostrazione.
La posto qui nel caso a qualcuno servisse in futuro: http://www.formazione.unimib.it/DATA/bacheca/File/infav2-0708/9-Tesi_CT_e_indecidibilita(1).pdf
Dopo tanto googlare, ho trovato un pdf che faceva al caso mio, non contiene tutte le spiegazioni rigorose, ma in compenso evidenzia bene i vari passaggi di quella dimostrazione.
La posto qui nel caso a qualcuno servisse in futuro: http://www.formazione.unimib.it/DATA/bacheca/File/infav2-0708/9-Tesi_CT_e_indecidibilita(1).pdf
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo