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.
Cos'è un algoritmo modifica
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:
...
Funzioni parziali ricorsive modifica
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.
Tesi di Church-Turing modifica
Se una funzione è calcolabile secondo un qualsiasi formalismo esistente e non, allora lo è anche con una macchina di Turing.
Bibliografia modifica
- 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. Trascrizione del testo, su digiTANTO.it.
Voci correlate modifica
Altri progetti modifica
Wikimedia Commons contiene immagini o altri file sulla teoria della calcolabilità
Collegamenti esterni modifica
- (EN) computability theory, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
| Controllo di autorità | J9U (EN, HE) 987007545779505171 |
|---|
