Questo blog si riferisce alla lezione che ho tenuto mercoledì 10 dicembre.
Nella lezione ho spiegato cosa è la Tesi di Church: "Ogni funzione calcolabile è calcolabile da una Macchina di Turing". Ho fatto vedere come l'inverso di questa affermazione ("Ogni funzione calcolabile da una Macchina di Turing è calcolabile") è ovviamente vera, e ho spiegato che la Tesi di Church è ritenuta vera dalla comunità scientifica (ed è alla base dell'informatica) e non ha mai trovato una refutazione (non è mai stata trovata una funzione calcolabile che non possa essere calcolata da una macchina di Turing). Ho spiegato anche perché non possa essere trovata una "dimostrazione" della Tesi di Church: essa richiederebbe di conoscere cosa sia una funzione calcolabile "generica", ma è proprio per capire cosa sia una funzione calcolabile "generica" è stato introdotto il concetto di Macchina di Turing...
Nella lezione ho trattato anche il concetto di funzione "trattabile" : funzione che non solo è calcolabile, ma ha ache almeno un programma che viene eseguito in "tempo polinomiale" (ossia non in "tempo esponenziale").
Ho slegato inoltre il concetto di macchina "deterministica" (una macchina di Turing che non ha due istruzioni diverse con lo stessa condizione) e di macchina "non-deterministica" (una macchina di Turing che ha istruzioni diverse con la stessa condizione).
E ho spiegato cosa siano le classi P e NP (entrambe sono classi di funzioni "trattabili", P è la classe delle funzioni che sono calcolabili in tempo polinomiale con macchina di Turing deterministica, NP è la classe delle funzioni che sono calcolabili in tempo polinomiale con macchina di Turing non-deterministica).
Ho mostrato infine come sia ovvio che P è inclusa in in NP, e ho spiegato che è un problema ancora aperto quello se NP sia inclusa in P. Dunque è aperto il problema "P=NP?".
Nella lezione ho spiegato cosa è la Tesi di Church: "Ogni funzione calcolabile è calcolabile da una Macchina di Turing". Ho fatto vedere come l'inverso di questa affermazione ("Ogni funzione calcolabile da una Macchina di Turing è calcolabile") è ovviamente vera, e ho spiegato che la Tesi di Church è ritenuta vera dalla comunità scientifica (ed è alla base dell'informatica) e non ha mai trovato una refutazione (non è mai stata trovata una funzione calcolabile che non possa essere calcolata da una macchina di Turing). Ho spiegato anche perché non possa essere trovata una "dimostrazione" della Tesi di Church: essa richiederebbe di conoscere cosa sia una funzione calcolabile "generica", ma è proprio per capire cosa sia una funzione calcolabile "generica" è stato introdotto il concetto di Macchina di Turing...
Nella lezione ho trattato anche il concetto di funzione "trattabile" : funzione che non solo è calcolabile, ma ha ache almeno un programma che viene eseguito in "tempo polinomiale" (ossia non in "tempo esponenziale").
Ho slegato inoltre il concetto di macchina "deterministica" (una macchina di Turing che non ha due istruzioni diverse con lo stessa condizione) e di macchina "non-deterministica" (una macchina di Turing che ha istruzioni diverse con la stessa condizione).
E ho spiegato cosa siano le classi P e NP (entrambe sono classi di funzioni "trattabili", P è la classe delle funzioni che sono calcolabili in tempo polinomiale con macchina di Turing deterministica, NP è la classe delle funzioni che sono calcolabili in tempo polinomiale con macchina di Turing non-deterministica).
Ho mostrato infine come sia ovvio che P è inclusa in in NP, e ho spiegato che è un problema ancora aperto quello se NP sia inclusa in P. Dunque è aperto il problema "P=NP?".
Nessun commento:
Posta un commento