Teoria della calcolabilità

Da Wikipedia, l'enciclopedia libera.

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, e che a livello pratico potrebbero essere proibitive). Questa disciplina è comune sia alla matematica che 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, anche in questo caso senza contare le limitazioni imposte dai costi, dal tempo, 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 input).

Che cos'è un algoritmo[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Algoritmo.

Che cos'è un algoritmo? Non è immediato fornire una buona definizione, cioè una definizione utilizzabile in ambito matematico. Si può immaginare un algoritmo come una sequenza finita di istruzioni che definiscano in modo chiaro e non ambiguo le operazioni da eseguire per raggiungere un risultato. Possiamo riconoscere intuitivamente che cosa sia un algoritmo da che cosa non lo sia. 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 possano calcolare in linea di principio, è la stessa.

Poiché, quando scriviamo un programma in un qualsivoglia linguaggio di programmazione, stiamo fornendo una sequenza di istruzioni per produrre un certo output, si può pensare ad un algoritmo come ciò che nasconde una funzione che prenda in input dei numeri naturali e restituisca in output numeri naturali. Se un algoritmo computa su un insieme qualunque A, è possibile associare ad esso una funzione parziale:

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

Funzioni parziali ricorsive[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi 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.

Tesi di Church-Turing[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Tesi di Church-Turing.

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

Insiemi e predicati[modifica | modifica sorgente]

Decibili (ricorsivi), non decibili, ricorsivamente enumerabili, produttivi, creativi, semplici

Riduzioni[modifica | modifica sorgente]

m-reduction, Turing reduction

Bibliografia[modifica | modifica sorgente]

  • 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 0471095850
  • Piergiorgio Odifreddi, Classical Recursion Theory (1989 e 1999), due volumi, North Holland.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica