Computabilità

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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[modifica | modifica wikitesto]

Una funzione si dice computabile se esiste un algoritmo che la calcola. In termini matematici, si dice che un algoritmo calcola una funzione se, per ogni possibile valore della variabile indipendente, assegnando questo valore come input dell'algoritmo, l'algoritmo fornisce come risultato .

Esempio di una funzione[modifica | modifica wikitesto]

Esempio. La funzione , per , è computabile. Infatti sono noti vari algoritmi per trovare il doppio di un numero naturale. L'esempio precedente si riferisce all'insieme dei numeri naturali, anziché all'insieme 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à[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]