Da pagina 170 del libro di testo
Un’istanza di un problema è un caso specifico del problema stesso (perché sono stati fissati i dati del problema).
171 – Esecutori
Fino alla fine del ‘800 sono stati proposti congegni di calcolo di tipo meccanico
| Autore | Sistema di calcolo |
|---|---|
| Wilhelm Schickard | Orologio calcolante |
| Blaise Pascal | Pascalina |
| Charles Babbage | Macchina differenziale Macchina analitica |
Nel primo ‘900 sono stati proposti modelli astratti, formali, di esecutori che potessero calcolare la risposta per ogni istanza di un problema.
| Autore | Sistema di calcolo |
|---|---|
| Alonzo Church | Funzioni, Lambda calcolo |
| Stephen C. Kleene | Funzioni, Funzioni ricorsive parziali |
| Andrey A. Markov | Sistemi di riscrittura, sistema semi-Thue |
| Emil L. Post | Sistemi di riscrittura, sistemi formali |
| Alan M. Turing | Macchina di Turing |
I primi esecutori sono dei sistemi di calcolo di tipo logico-matematico e permettono di calcolare la risposta applicando delle regole ad un insieme iniziale di formule che rappresentano l’istanza del problema.
La macchina di Turing è il modello più vicino alla realtà che ha permesso di costruire i primi computer.
Per ogni coppia di modelli di calcolo è stato dimostrato che i problemi computabili coincidono.
Quindi non c’è alcun vantaggio teorico fra l’uno e l’altro.
Quindi conviene utilizzare il sistema di calcolo più pratico/semplice.
180 – Macchina universale
Se si definisce un insieme minimo di istruzioni riconosciute, ed eseguite, da una macchina allora essa diventa un sistema di calcolo universale.
Non è più necessario progettare fisicamente la macchina per un certo problema ma è sufficiente progettare un algoritmo, risolutivo per il problema, e farlo eseguire per una certa istanza.
170 – Calcolabilità
La definizione di calcolabilità cambia con l’evoluzione dei modelli e delle tecnologie
| Esecutore | Problema Dati_Esecutore_Risposta | Un problema è computabile, calcolabile, se esiste un esecutore che produce, in tempo finito, la risposta corrispondente a qualsiasi istanza del problema. |
| Macchina universale | Problema Algoritmo Dati_Esecutore_Risposta | Un problema è computabile, calcolabile, se esiste un algoritmo per un esecutore che produce, in tempo finito, la risposta corrispondente a qualsiasi istanza del problema. |
| Ling_di_progetto Ling_di_programmazione | Problema Algoritmo Programma Dati_Computer_Risposta | Un problema è computabile, calcolabile, se esiste un algoritmo, tradotto in un programma, eseguito da un computer che produce, in tempo finito, la risposta corrispondente a qualsiasi istanza del problema. |
181 – Tesi di Church
L’insieme dei problemi computabili coincide con quello dei problemi computabili con la macchina di Turing.
Si ipotizza che la macchina di Turing (e anche gli altri sistemi di calcolo) sia sufficiente per tutti i problemi computabili.
La tesi di Church chiude la porta all’esistenza di sistemi di calcolo più potenti.
I problemi
I problemi sono delle richieste che richiedono all’uomo un certo impegno fisico e/o intellettuale.
Ma tra tutti i problemi, di quali si occupa l’informatica?
| Assurdi? | Perché perdere tempo se la richiesta è assurda… |
| Impossibili? | Pur interessanti, è dimostrato che non ammettono soluzione, quindi… sono PROBLEMI NON COMPUTABILI |
| Intrattabili? | Le risorse hardware e/o il tempo necessario per ottenere la soluzione sono proibitivi, quindi… sono PROBLEMI INTRATTABILI |
| Banali? | Esiste un dispositivo dedicato adatto allo scopo, quindi… |
| Interessanti? | Se il problema non è assurdo, impossibile, intrattabile, banale allora… |