algoritmo

(ant. algorismo), sm. [sec. XIII; dal nome arabo al-Khuwārizmī]. Termine derivato dal nome del matematico arabo del sec. IX Muḥammad ibn Mūsā al-Khuwārizmī, latinizzato in Algorithmi, designante inizialmente le operazioni aritmetiche. Nel linguaggio corrente il termine indica oggi un sistema di regole e di procedure di calcolo ben definite che portano alla soluzione di un problema in un numero finito di passi (operazioni). § In particolare, un algoritmo richiede che ogni operazione sia computabile in tempo finito da un sistema con risorse finite, e che al suo termine sia definito, in modo non ambiguo, il prossimo passo da eseguire, cosicché l'intero processo abbia un termine. Per esempio, un algoritmo per calcolare il fattoriale di un numero può essere il seguente: 1) assegna il valore di ingresso alla variabile n; 2) se n è negativo termina restituendo il messaggio “ingresso errato”; 3) assegna il valore 1 alla variabile m; 4) se n è uguale a 0 vai al passo 8; 5) moltiplica il valore di m per il valore di n e metti il risultato in m; 6) aggiorna il valore di n decrementandolo di 1; 7) se n è maggiore di 1 torna al passo 5; 8) termina restituendo il valore corrente di m. Si noti che un algoritmo può essere espresso in qualsiasi linguaggio, in questo caso il linguaggio naturale, purché ogni suo passo sia interpretato in modo non ambiguo ed eseguito da un qualche agente computazionale. Gli algoritmi non si limitano al risolvimento di problemi numerici, al contrario, qualsiasi problema la cui soluzione sia descrivibile in maniera algoritmica, può essere risolta mediante un elaboratore elettronico, esprimendo l'algoritmo per la sua soluzione tramite un qualche linguaggio di programmazione interpretabile dall'elaboratore. Vedi anche algoritmo genetico. § Nella logica moderna si è cercato di giungere a una nozione astratta di algoritmo, vale a dire comprendente in sé, come casi particolari, tutti gli algoritmi possibili. Diversi autori (A. Church, A. M. Turing, A. Markov e altri) hanno dato in termini diversi la definizione di algoritmo: Church in termini di λ computabilità, Turing nell'ambito della sua teoria delle macchine e Markov nella sua teoria degli algoritmi normali. Tutte queste formulazioni risultano equivalenti nel senso che, operate opportune traduzioni, gli algoritmi dati da queste varie definizioni sono gli stessi.Un risultato fondamentale della teoria degli algoritmi è che non ne può esistere uno (espresso come sequenza di istruzioni eseguibili da una macchina di Turing) che permetta di stabilire se un qualsiasi algoritmo termina o meno.