Problema, esecutore
I problemi
I problemi sono eventi che richiedono all'uomo un certo impegno fisico e/o intellettuale.Ma tra tutti i problemi, di quali si occupa l'informatica?
| Improponibili? | Nessuno è disposto a perderci tempo ... |
| Impossibili? | Pur interessanti, è noto che non esiste un algoritmo ... NON COMPUTABILI |
| Intrattabili? | Le risorse hardware e/o il tempo necessario per ottenere la soluzione sono proibitivi ... |
| Banali? | Esiste un dispositivo dedicato adatto allo scopo ... |
| Interessanti? | Se il problema non è impossibile, intrattabile, improponibile, banale allora ... |
Un'istanza di un problema è un caso specifico, particolare del problema stesso (perché sono fissati i dati del problema).
Gli esecutori
Da sempre l'uomo desidera avere un suo sostituto che lo sollevi dalla fatica e dalle lunghe attese necessarie per avere la risposta a ogni istanza di un certo problema (qualsiasi problema...)| Umanoidi | Automa, androide, schiavo, macchina, robot, cyborg, .... |
| Dispositivi | Ascensore, calcolatrice, decoder, pianola, ... |
| Letteratura | Golem, Frankenstein, ... |
| Cinema | Metropolis, Blade Runner, Terminator, Robocop, Io e Caterina, ... |
Computabilità
Un problema è computabile, calcolabile, se esiste un (algoritmo per un) esecutore che è capace di produrre, in tempo finito, la risposta corrispondente a qualsiasi istanza del problema.Sistemi di calcolo
Nel primo '900 sono stati proposti molti modelli astratti, formali, di esecutori che potessero calcolare la risposta per ogni istanza di un problema| Autore | Sistema di calcolo |
|---|---|
| Stephen Kleene | Funzioni ricorsive (parziali) |
| Emil Post | Sistemi di riscrittura (sistemi formali) |
| Alonso Church | Lambda calcolo |
| Alan Mathison Turing | Macchina di Turing |
| John Von Neumann | Macchina a registri |
I primi tre 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 logico-matematiche che rappresentano l'istanza del problema...
La macchina di Turing e la macchina a registri sono dei modelli più fisici che hanno permesso di costruire le prime macchine calcolatrici.
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.
È stato dimostrato che gli insiemi dei problemi computabili dai diversi sistemi di calcolo, finora proposti, sono equivalenti.
Quindi conviene utilizzare il sistema di calcolo più pratico perché non c'è alcun vantaggio reale fra l'uno e l'altro.
Tesi di Church
L'insieme dei problemi computabili coincide con quello della macchina di Turing.
Si ipotizza che la macchina di Turing sia sufficiente per tutti i problemi computabili (e quindi lo anche gli altri sistemi di calcolo).In linea di principio tutti i computer hanno le stesse capacità di calcolo...
