Computabilità

La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi. Fra i suoi fondatori vi è Alan Turing.

Caratteristiche di esistenza

Una funzione si dice computabile se esiste un algoritmo che la calcola. In termini matematici, si dice che un algoritmo calcola una funzione $f(x)$ se, per ogni possibile valore $x_{0}$ della variabile indipendente, assegnando questo valore come input dell'algoritmo, l'algoritmo fornisce come risultato $f(x_{0})$.

Esempio di una funzione

Esempio. La funzione $f(x)=2x$, per $x\in \mathbb {N}$, è computabile. Infatti sono noti vari algoritmi per trovare il doppio di un numero naturale. L'esempio precedente si riferisce all'insieme $\mathbb {N}$ dei numeri naturali, anziché all'insieme $\mathbb {R}$ dei reali. Questo perché i numeri reali, fatte salve alcune eccezioni, non possono essere effettivamente dati. Un numero è effettivamente dato se esiste un algoritmo che consente di trovare qualunque cifra si voglia trovare della sua rappresentazione decimale. Un algoritmo può essere visto come una Macchina di Turing. Sotto questo aspetto il concetto di algoritmo viene sottratto dall'ambito astratto e identificato con qualcosa di più concreto.

Caratteristiche di computabilità

Esistono molte altre formulazioni di ciò che è un algoritmo. La nozione di computabilità traduce rigorosamente, tramite la nozione di funzione e la nozione di algoritmo, la possibilità di svolgere un certo tipo di compito ovvero risolvere un certo tipo di problema applicando un procedimento automatico prestabilito. È molto importante sapere se un dato lavoro può essere svolto da una macchina, ovvero da una persona non in grado di prendere decisioni autonome, oppure è richiesta la presenza di una persona chiamata a decidere caso per caso, o almeno nei casi più difficili, correndo anche il rischio di sbagliare. Molti problemi possono essere risolti dalle macchine, ma ne sono noti alcuni non risolubili da nessuna macchina. Il più classico esempio di problema non risolubile in modo automatico è il cosiddetto Problema della fermata.

Voci correlate

• Computazione
• Teoria della computabilità
• Teoria della computazione
• Teoria della complessità computazionale

Collegamenti esterni

• (EN) computability, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Computabilità, su MathWorld, Wolfram Research.