Strumenti Utente

Strumenti Sito


Action disabled: source
db:teoria_della_computabilita

Teoria della computabilità

Approfondimenti

Info

Quest'argomento non è collegato ad altri approfondimenti correlati. Si consiglia, in ogni caso, di controllare sempre [ l'Indice ] degli Approfondimenti

Questa pagina è solo improntata in attesa di completamento da parte dei Collaboratori. Se sei interessato a collaborare attivamente con Extrapedia, leggi come fare [ Collabora ]

La Teoria della computabilità, nota anche come Teoria della ricorsione, è una branca della Logica matematica, dell'Informatica e della Teoria della computazione che ebbe origine negli anni '30 con lo studio delle funzioni computabili e dei gradi di Turing. Da allora, il campo è stato ampliato per includere lo studio della computabilità e della definibilità generalizzate. In queste aree, la Teoria della ricorsione si sovrappone alla teoria delle prove e alla teoria degli insiemi descrittivi efficaci.

Le domande di base affrontate dalla Teoria della ricorsione includono:

Che cosa significa per una funzione sui numeri naturali essere calcolabile? In che modo le funzioni non computabili possono essere classificate in una gerarchia in base al loro livello di non-capacità?

Sebbene vi sia una considerevole sovrapposizione in termini di conoscenze e metodi, i teorici della ricorsione matematica studiano la teoria della computabilità relativa, le nozioni di riduzione e le strutture di laurea; quelli nel campo dell'informatica si concentrano sulla Teoria della complessità computazionale, sui metodi e sui linguaggi formali.


Qualora alcuni link non funzionassero, si prega di comunicarlo allo Staff - staff@extrapedia.org


db/teoria_della_computabilita.txt · Ultima modifica: 13/04/2019 16:08 (modifica esterna)