Problemi ed esecutori

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… ce ne occupiamo

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 oppure che gli risparmi le 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, I robot, …

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.

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 che rappresentano l’istanza del problema…

La macchina di Turing e la macchina a registri sono dei modelli più vicini alla realtà 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 teorico 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 sono anche gli altri sistemi di calcolo).

Equivale a

Tutti i computer hanno la stessa capacità di calcolo.
Sia quelli attuali che quelli futuri…