01. Elementi di teoria della computabilità

Con il recente enorme sviluppo delle discipline informatiche e l’uso sempre più diffuso dei calcolatori, il concetto di algoritmo ha assunto un ruolo centrale in ambito scientifico. Fin dall'antichità gli algoritmi hanno accompagnato lo sviluppo della matematica, ma solo a partire dalla seconda guerra mondiale sono stati fatti oggetto di indagine diretta, dando origine ad una nuova teoria matematica, detta teoria della computabilità.

Intuitivamente, un algoritmo è un procedimento di calcolo che si basa sull'applicazione di un numero finito di regole (o istruzioni) che determinano in modo automatico tutti i singoli passi del procedimento stesso.

Introduciamo le seguenti definizioni:

• • Un problema formulato matematicamente (cioè una proprietà o una relazione aritmetica) è detto decidibile se e solo se esiste un procedimento automatico che consente di stabilire se esso sussiste o non sussiste.

  • Una funzione o una operazione aritmetica è detta calcolabile (o computabile) se e solo se esiste un procedimento automatico che consente di calcolarne i valori in corrispondenza dei loro argomenti per i quali tali valori esistono.

E' bene osservare che esistono problemi non decidibili e funzioni non calcolabili.

Il problema della decidibilità è affrontato dal teorema di Turing che dimostra come il problema della fermata sia un problema non decidibile.

Semplificando al massimo, il problema della fermata consiste nel trovare un procedimento automatico (cioè un algoritmo) che sia in grado di stabilire se, scelto liberamente un programma P tra tutti i possibili programmi, esso completerà la sua elaborazione su un certo input I.

Da un punto di vista pratico emerge che alcuni problemi matematici non possono essere affrontati algoritmicamente, indipendentemente dalla potenza dei computer a disposizione.

La teoria della computabilità introduce anche una misura di efficienza per gli algoritmi: la complessità computazionale.

Questa misura mette in relazione la "taglia" del problema e il numero di istruzioni che l'algoritmo deve svolgere per raggiungere la soluzione.

Ad esempio, prendiamo in esame un programma che riceve in input una stringa di caratteri e riproduce in output tutte le possibili permutazioni della stringa data.

Dal calcolo combinatorio sappiamo che le permutazioni possibili dipendono dal numero di caratteri ricevuti in input: se la taglia del problema è n (cioè se i caratteri in input sono n) le possibili permutazioni sono n! (fattoriale di n).

Per dare un'idea, se in input è data una stringa di 100 caratteri in output avremo 100! ≈ 9*10¹⁵⁷ differenti stringhe.

Attenzione, perché nessun computer oggi disponibile è in grado di completare questa elaborazione in un tempo utile (ad esempio in 100 anni!).

Consideriamo un secondo programma che riceve in input ancora una stringa di caratteri e che in output riproduce la stessa stringa in ordine inverso.

Anche in questo caso il numero di istruzioni dipende dalla taglia dell problema, ma è banale osservare che se la stringa in ingresso è formata da n caratteri, in output dovrà riprodurre sempre n caratteri. Consideriamo ancora come input una stringa di 100 caratteri: l'elaborazione da parte di un computer moderno si completerà in una frazione di secondo!

Deduciamo che il primo dei problemi analizzati è computazionalmente più complesso del secondo.

Inoltre si può intuire che un problema computazionalmente complesso diventa intrattabile a mano a mano che la taglia del problema aumenta.

In generale diremo che un problema (su un certo input) è intrattabile algoritmicamente se non è disponibile un algoritmo in grado di giungere alla soluzione in un tempo e con un consumo di risorse (memoria) accettabili.

Sito: 7ecnologie

Sezione: 16. Calcolo numerico

Capitolo: 01. Elementi di teoria della computabilità

Indice dei capitoli: 00. Risorse - 01. Elementi di teoria della computabilità - 02. Soluzioni simboliche e numeriche - 03. Computer e calcolo numerico - 04. MATLAB/Octave - 05. Desmos - 06. WIRIS/calcme - 07. WolframAlpha