Teoria della calcolabilità
Da Wikipedia, l'enciclopedia libera.
Motivazione: definizione vaga, Cosa è un algoritmo non c'entra, c'è già la definizione di algoritmo su wikipedia. Segnalazione di --nicolaennio 20:56, 21 set 2006 (CEST)
La teoria della calcolabilità, della computabilità, o teoria della ricorsione cerca di comprendere cosa può essere effettivamente computato, ovvero quali funzioni ammettono un procedimento di calcolo automatico per ricavarne i valori. L'obiettivo principale è quello di rendere rigorosa (matematicamente formale) l'idea intuitiva di "funzione calcolabile" e scoprire quali siano le possibilità ed i limiti delle cose che ci proponiamo di calcolare. Questa disciplina è comune sia alla matematica che alla computer science. Da una parte l'approccio è quello di approfondire il concetto di calcolabile cercando di individuare le categorie di problemi teoricamente risolvibili e dall'altro mappare questo concetto su cosa i computer sono in grado di elaborare in linea di principio, ovvero senza restrizioni fisiche come, per esempio, costi, tempo, spazio di memoria. Per tali ragioni la teoria della calcolabilità è strettamente legata con la teoria della complessità il cui scopo è quello di vincolare l'idea di calcolabile ai suddetti limiti con particolare attenzione al tempo e allo spazio. 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 e più precisamente come funzioni che preso un determinato input ritornato un risultato.
Indice |
[modifica] Cosa è un algoritmo
Che cosa è un algoritmo? Non è immediato fornire una definizione che in realtà è una buona definizione, ovvero una definizione utilizzabile in ambito matematico. Si può immaginare un algoritmo come una sequenza finita di istruzioni che definiscono in modo chiaro e non ambiguo le operazioni da eseguire per raggiungere un obiettivo e possiamo riconoscere intuitivamente cosa è un algoritmo da cosa non lo è. 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 cattura pienamente cosa sia un algoritmo. Per ottenere una definizione accettabile sono stati pensati diversi modi equivalenti, per 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 essere fra loro equivalenti con la conseguenza che la potenza di calcolo, ovvero cosa possono calcolare in linea di principio, è la stessa.
Poiché quando scriviamo un programma in un qualsivoglia linguaggio di programmazione si sta fornendo una sequenza di istruzioni che produce un certo output, si può pensare ad un algoritmo come un qualcosa che nasconde una funzione che prende in input dei numeri naturali e restituisce numeri naturali. Se un algoritmo computa su un insieme qualunque A è possibile associare ad esso una funzione parziale:
...
[modifica] Funzioni parziali ricorsive
 |
Per approfondire, vedi la voce Funzione ricorsiva. |
zero, succ, proiezione, composizione, ricorsione primitiva, minimizzazione ... esempi ...
[modifica] Tesi di Church-Turing
|
Per approfondire, vedi la voce Tesi di Church-Turing. |
Secondo questa tesi, se una funzione è calcolabile secondo un qualsiasi formalismo esistente e non, allora lo è anche con una macchina di Turing.
[modifica] Insiemi e predicati
Decibili (ricorsivi), non decibili, ricorsivamente enumerabili, produttivi, creativi, semplici
[modifica] Riduzioni
m-reduction, Turing reduction
[modifica] Bibliografia
- 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
