Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] α non è accettata, ovvero la risposta è 0, se la macchina si arresta in uno stato di S−F. La teoriadellacomputabilità insegna che possono esistere stringhe per cui la macchina non si arresta mai. In linea teorica anche queste stringhe non sono ...
Leggi Tutto
Matematico statunitense (New York 1947). Ha apportato importanti contributi alla teoria algoritmica dell'informazione (AIT), combinando il metodo di C. Shannon (') e la teoriadellacomputabilità di A.M. [...] Turing ('). Autore di molti saggi, i suoi studi hanno portato a dimostrare l'esistenza della casualità anche in aritmetica. ...
Leggi Tutto
computabile
computàbile [agg. Der. dell'ingl. computable, che è dal lat. computabilis "che si può calcolare", "di cui si può o si deve tenere conto", già reso con l'it. calcolabile] [ALG] [FAF] [INF] [...] o, in altri termini, le grandezze che possono essere calcolate con un elaboratore adeguatamente programmato; la teoriadellacomputabilità, o della ricorsività, studia i limiti teorici di un tale procedimento di calcolo. ◆ [INF] Funzione c.: funzione ...
Leggi Tutto
ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoriadella r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto [...] di I). I concetti di decidibilità, costruibilità e computabilità sono così strettamente collegati che, non appena si riesca di Gödel costituiscano un passo fondamentale per utilizzare la teoriadella r. nei problemi di decisione. Infatti, avvenuta l ...
Leggi Tutto
Logica matematica
Abraham Robinson
*La voce enciclopedica Logica matematica è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un’introduzione di Gabriele Lolli e un saggio di Beppo [...] naturale trattare in primo luogo la nozione di calcolabilità (o ‛computabilità') nel sistema dei numeri naturali, vale a dire cercare di stabilire in quali condizioni una funzione dellateoria dei numeri - cioè una funzione con argomento e valori nei ...
Leggi Tutto
La grande scienza. Geometria non commutativa
Alain Connes
Geometria non commutativa
Se si pensa che la geometria sia strettamente legata al nostro modello di spazio-tempo, allora la teoria generale [...] 1982) abbiamo introdotto una K-teoria definita geometricamente che contempla in particolare gruppi discreti, gruppi di Lie, azioni di gruppi e foliazioni. Le proprietà principali sono la computabilità e la semplicità delle definizioni. Nel caso dei ...
Leggi Tutto
L'Universo matematico
John D. Barrow
(Astronomy Centre, University of Sussex, Brighton, Gran Bretagna)
Parte di questo saggio è stata pubblicata sotto il titolo Perché il mondo è matematico? Roma-Bari, [...] l'abilità di comprendere cose come la teoria quantistica, i buchi neri, la teoriadella relatività, pur non avendo di per sé umana.
La computabilità
Il costruttivismo, però, ci insegna qualcosa sul carattere matematico della natura. Possiamo vedere ...
Leggi Tutto
Geometria non commutativa
Alain Connes
Se si pensa che la geometria sia strettamente legata al nostro modello di spazio-tempo allora la teoria generale della relatività dà chiaramente ragione a Carl [...] F. Baum abbiamo introdotto una K-teoria definita geometricamente che contempla in particolare gruppi discreti, gruppi di Lie, azioni di gruppi e foliazioni. Le proprietà principali sono la computabilità e la semplicità delle definizioni. Nel caso dei ...
Leggi Tutto
Computazione, teoriadella
Fabrizio Luccio
La necessità del calcolo, pur riconosciuta dall'uomo in tutte le epoche storiche, ha condotto solo in tempi relativamente recenti a una sistemazione teorica [...] lo sviluppo dei calcolatori a programma memorizzato. È questa l'origine dei due assi portanti dellateoriadella computazione, cioè la computabilità e la complessità di calcolo.
Il secondo problema di Hilbert sulla dimostrazione di compatibilità ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. Teoriadella ricorsivita
Piergiorgio Odifreddi
Teoriadella ricorsività
La teoriadella ricorsività affronta lo studio delle funzioni con lo [...] Cinquanta, con un interesse via via crescente, la teoriadella ricorsività ha cercato di svincolarsi dall'approccio puramente numerico e di estendere la propria ricerca alla nozione di computabilità su oggetti di varia natura. Una tale estensione è ...
Leggi Tutto
computabile
computàbile agg. [dal lat. computabĭlis]. – Che si può computare; di cui si può o si deve tener conto: periodo di servizio militare c. ai fini della pensione. In logica matematica e in informatica teorica, detto di una funzione...