Teorema della fermata e problemi indecidibili
Dimostrazione dettagliata del teorema della fermata di Touring. (4 pagine formato doc)
Un programma P, scritto nel linguaggio L, può essere visto come :
una funzione parziale PL : D → D tale che PL (INPUT) = (OUTPUT)
se l’esecuzione di PL sul dato in ingresso Input termina e produce come risultato Output.
La funzione sarà definita nel caso in cui il dato in ingresso produce un risultato.
Non sarà definita nel caso in cui sul dato in ingresso Input non termina.
L’espressione “non termina” non deve essere ricondotta all’analisi della complessità O(fn) associata al generico problema, gestito dal programma P scritto nel linguaggio L, ma ci dovrà consentire di introdurre il concetto di calcolabilità associato ad un problema di decisione.
L’analisi della complessità di un problema di decisione consiste nel considerare: il tempo, lo spazio in memoria e il costo derivante da una singola istruzione, all’interno di un contesto.
Con questa metodologia riusciamo a distinguere i problemi di decisione in molteplici classi ( non polinomiale, polinomiale, ecc) fra cui alcuni di questi detti indecidibili che si distinguono per non avere un algoritmo in grado di dare una soluzione al loro problema.
Non abbiamo una sequenza finita di istruzioni che definiscono in modo chiaro e non ambiguo le operazioni da seguire per raggiungere un obbiettivo.
.