L’algoritmo è una sorta di rappresentazione formale di tutto ciò che accade nel mondo

A volte sembra che l’algoritmo sia un elemento difficile da comprendere e che non ha molta aderenza con la realtà ed invece si deve tenere presente che ogni singola azione che ogni giorno effettuiamo possono essere riassunte in un insieme di operazioni. Entrando nella specificità della definizione si deve tenere presente che un algoritmo è la risoluzione ad un problema mediante un numero finito di operazioni semplici e chiare in modo quindi che non possano esserci ambiguità di sorta. Naturalmente questo concetto è alla base dell’informatica perché si entra nei problemi della calcolabilità diventando una vera e propria colonna della programmazione. In buona sostanza si deve tenere presente che se si decide di prendere la

Proprietà fondamentali

Questo elemento per essere funzionante deve avere delle caratteristiche peculiari che riescano a portare a termine una determinata applicazione in un determinato numero di passi. Ma per far in modo che questi siano realmente utili è necessario che posseggano le seguenti caratteristiche:

  • atomicità: ogni passono non può essere ulteriormente scomponibile;
  • non ambiguità: ogni passo dev’essere scritto in modo tale che non si vada a creare ambiguità da parte dell’esecutore sia esso umano o artificiale;
  • finitezza: l’algoritmo dev’essere composto da un numero finito di passi;
  • terminazione: si lega molto bene col passo precedente perché impone che l’algoritmo non può essere infinito e deve avere un termine.
  • effettività: l’algoritmo deve portare ad un risultato univoco.

Si potrebbe quindi affermare che l’algoritmo deve dare un in lasso di tempo finito i risultati sperati ovvero se da un determinato input si ottiene un determinato output, utilizzando termini più aderenti all’informatica.

La Macchina di Turing

Il naturale sviluppo che porta l’algoritmo è la Macchina di Turing, chiamata così dal suo scopritore Alan Turing, che si basa sul funzionamento di una macchina che ha come unico scopo quello di manipolare i dati su un nastro praticamente infinito. In pratica si va a parlare di una macchina in grado di eseguire gli algoritmi teoricamente all’infinito.

L’algoritmo nella teoria della computabilità

Dalla Macchina di Turing nacque la teoria della computabilità la tesi di Church-Turing che afferma che ogni problema umanamente calcolabile può essere risolto da una macchina di Turing. Ad Alonzo Church  si deve il lambda calcolo che prenderemo in analisi in seguito.