Algoritmi e calcolabilità - Lezione in semi-presenza

Lezione in semi-presenza

6. Algoritmi e realizzazioni meccaniche degli stessi

Nel procedere, ne esistono una miriade di questi algoritmi, alcuni ci sono stati insegnati e altri li hanno tralasciati. Il concetto di algoritmo, così come ci è stato insegnato, esiste già da tempo così come, le macchine non le abbiamo pensate noi nel XX secolo. L’elemento algoritmico più antico che l’umanità abbia avuto è l’orologio. Esso realizza un algoritmo particolare ovvero quello di misurare il tempo. Misura le ore e i minuti (ma anche i secondi) attraverso due lancette: quella più lunga dei minuti e quella più corta delle ore. Ad ogni giro intero della lancetta dei minuti, la lancetta delle ore fa un passo in avanti.

Pascal pensò ad altre macchine partendo dall’algoritmo della somma. Non è oggi che sono stati scoperti gli algoritmi e neppure oggi che essi sono stati applicati a delle macchine, semplicemente la tecnologia è avanzata.

Il problema che risolve l’algoritmo può essere parametrico. L’algoritmo è una cosa distinta rispetto all’esecuzione dello stesso e all’invenzione dello stesso.

Perché un algoritmo è finito? Perché può essere scritto in un tempo finito, non può essere infinito. Infinito, invece, può essere un processo. Deve essere possibile scrivere l’algoritmo che per questo deve essere contenibile in uno spazio finito. Dall’altra parte, l’esecuzione di un algoritmo, può durare all’infinito poiché un processo può durare all’infinito.

L’algoritmo è una sequenza di istruzioni, mentre il processo è una sequenza di passi. Un passo è lo stato della variabile A e della variabile B. ad esempio, per sommare 45 e 63, bisognerà fare un certo numero di passi.

Anche per mettere a posto dei fogli si adotta una procedura. Possono essere usate diverse procedure, diversi algoritmi. Il migliore è quello più veloce, quello che se applicato impiega meno tempo.