Computabilità

Questa pagina sull'argomento matematica sembra trattare argomenti unificabili alla pagina Teoria della calcolabilità.

---

Puoi contribuire unendo i contenuti in una pagina unica. Segui i suggerimenti del progetto di riferimento.

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

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

Esempio. La funzione ${\displaystyle f(x)=2x}$, per ${\displaystyle 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 ${\displaystyle \mathbb {N} }$ dei numeri naturali, anziché all'insieme ${\displaystyle \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.

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.

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

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

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica