Teoria della calcolabilità

La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico. In altre parole, essa cerca di determinare se una data funzione è teoricamente calcolabile a prescindere dal fatto che sia anche trattabile, cioè a prescindere dalla quantità di risorse che la sua esecuzione richiede in termini di tempo o di memoria, che a livello pratico potrebbero essere proibitive. Questa disciplina è comune sia alla matematica sia all'informatica.

Di conseguenza l'obiettivo principale è dare una definizione formale e matematicamente rigorosa dell'idea intuitiva di funzione calcolabile. Da una parte l'approccio è quello di approfondire il concetto di calcolabilità, cercando di individuare le categorie di problemi che sono teoricamente risolvibili, e dall'altra mappare questo concetto su ciò che è teoricamente calcolabile sui computer, sempre senza considerare le limitazioni imposte dai costi, dal tempo e dalla quantità di memoria impiegata.

Un altro importante aspetto è quello di definire matematicamente il concetto di algoritmo in modo che i programmi possano essere concretamente pensati in termini di oggetti matematici, più precisamente come funzioni che restituiscono un determinato risultato a partire da un certo insieme di dati in ingresso.

Lo stesso argomento in dettaglio: Algoritmo.

Una prima definizione di algoritmo è la seguente: un algoritmo è una sequenza finita di istruzioni che definiscono in modo chiaro e non ambiguo le operazioni da eseguire per raggiungere un risultato. Per esempio, ragionando ad un alto livello di astrazione,

• Avanza 5 passi
• Gira a sinistra
• Avanza 7 passi

può essere un algoritmo per raggiungere una determinata posizione. Questa definizione però non esaurisce pienamente il concetto di che cosa sia un algoritmo. Per ottenere una definizione accettabile sono stati pensati diversi modi equivalenti, ad esempio mediante le macchine di Turing, le funzioni parziali ricorsive, i sistemi di Post e Markov e le macchine a registri, parenti stretti dei moderni elaboratori. Tutti questi metodi sono stati dimostrati fra loro equivalenti, con la conseguenza che la potenza di calcolo, cioè che cosa possono calcolare in linea di principio, è la stessa.

Poiché quando si scrive un programma in un qualsiasi linguaggio di programmazione si fornisce una sequenza di istruzioni per produrre un certo risultato, si può dire che un algoritmo è ciò che nasconde una funzione che prende in ingresso dei numeri naturali e restituisce in uscita numeri naturali. Se un algoritmo computa su un insieme qualunque A, è possibile associare ad esso una funzione parziale:

${\displaystyle f:A^{n}\rightarrow A^{m}}$ ...

Lo stesso argomento in dettaglio: Funzione ricorsiva.

Le funzioni parziali ricorsive sono un esempio di un formalismo atto a definire il concetto di funzione intuitivamente calcolabile.

Si può dimostrare che il formalismo delle funzioni parziali ricorsive ha la stessa espressività di quello della macchina di Turing. La dimostrazione si basa sull'implementazione di un interprete per una macchina di Turing tramite funzioni parziali ricorsive.

Lo stesso argomento in dettaglio: Tesi di Church-Turing.

Se una funzione è calcolabile secondo un qualsiasi formalismo esistente e non, allora lo è anche con una macchina di Turing.

• Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; Franco Angeli Editore: Linguaggi, Modelli, Complessità (2003) (ISBN 88-464-4470-1)
• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
• Piergiorgio Odifreddi, Classical Recursion Theory (1989 e 1999), due volumi, North Holland.
• Andrea de Prisco, Teoria della computabilità (JPG), in MCmicrocomputer, n. 58, Roma, Technimedia, dicembre 1986, pp. 150-153, ISSN 1123-2714 (WC · ACNP). Trascrizione del testo, su digiTANTO.it.

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

• Wikimedia Commons contiene immagini o altri file sulla teoria della calcolabilità

• (EN) Denis Howe, computability theory, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica