decidibilita
decidibilità termine utilizzato nella teoriadellacalcolabilità per indicare l’esistenza di una procedura algoritmica che permetta di stabilire, in un numero finito di passi, se una data [...] il suo insieme complementare. Nel contesto dellateoriadella ricorsività, gli insiemi decidibili e semidecidibili ; per questo motivo il problema della decidibilità è strettamente collegato al tema dellacalcolabilità di una funzione.
Un calcolo ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] . Ciò, in parte, è dovuto a limitazioni intrinseche evidenziate dalla teoriadellecalcolabilità e consistenti nella indecidibilità di molti problemi di verifica delle proprietà di programmi (per es., la terminazione). Tuttavia, questa situazione ...
Leggi Tutto
STORIA DELLA MATEMATICA
Luigi Borzacchini
STORIA DELLA MATEMATICA
Il tempo della scienza senza tempo
La matematica è la più antica e la più immutabile delle discipline. Si può dire che la matematica [...] descrizione sintetica. Si può però sostenere che l’affermarsi del linguaggio logico, del formalismo, dellateoriadellacalcolabilità caratterizzino negli ultimi cent’anni una matematica solidamente strutturata su una base sintattica, nonostante le ...
Leggi Tutto
Probabilità
Gian-Carlo Rota e Joseph P.S. Kung
*La voce enciclopedica Probabilità è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un contributo di Marco Li Calzi.
sommario: 1. Introduzione. [...] complessità si è rivelato più efficace nella teoriadellacalcolabilità che in quella della probabilità.
Un tentativo più promettente di alterare i fondamenti della probabilità che appartengono alla teoria degli insiemi potrebbe avere origine nell ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. La topologia algebrica all'inizio del XX secolo
John McCleary
La topologia algebrica all'inizio del XX secolo
Le radici della topologia algebrica [...] di due gruppi non è in generale risolubile. Molto più tardi, con lo sviluppo dellateoriadellacalcolabilità, si sarebbe dimostrato che il problema è effetivamente irrisolubile.
Il termine omotopia compare per la prima volta nell'articolo ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla [...] titolo, come l’evoluzione diretta dei contributi teorici dei logici che lavorano in quegli anni.
La nascita dellateoriadellacalcolabilità
Il meccanismo di ricorsione come mezzo per definire funzioni numeriche era già noto a Richard Dedekind e a ...
Leggi Tutto
Turing
Turing Alan Mathison (Londra 1912 - Wilmslow, Cheshire, 1954) logico e matematico inglese. È uno dei fondatori dellateoriadella → calcolabilità e quindi dell’informatica, e un pioniere dell’intelligenza [...] King’s College dell’università di Cambridge, dove studiò meccanica quantistica, logica e teoriadella probabilità. Laureatosi A. Church, che lavorava sugli stessi temi relativi alla calcolabilità e alla decidibilità. Nel 1939 ritornò a Cambridge e, ...
Leggi Tutto
funzione aritmetica
funzione aritmetica funzione definita sull’insieme N dei numeri naturali. Semplici funzioni aritmetiche sono, per esempio, la funzione successore, definita come s(n) = n + 1 per ogni [...] d(n) = m. Tutti i precedenti sono esempi di funzioni in cui anche il codominio è N e nella cosiddetta teoriadellacalcolabilità è questo il significato ristretto che si dà alla locuzione funzione aritmetica, dal momento che un effettivo sistema di ...
Leggi Tutto
Odifreddi
Odifreddi Piergiorgio (Cuneo 1950) matematico, logico e divulgatore scientifico italiano. Laureatosi in matematica nel 1973 a Torino, si è specializzato nelle università dell’Illinois e della [...] di Torino (1983-2007), e presso l’università Vita-Salute San Raffaele di Milano (2001-03), occupandosi di teoriadellacalcolabilità (Classical recursion theory, Teoria ricorsiva classica, 2 voll., 1989). Ha ideato e organizzato il Festival ...
Leggi Tutto
Discreto e continuo
Paolo Zellini
Matematica e intuizione
La matematica ha sempre cercato di stabilire un nesso tra il continuo e il discreto, il primo esemplificato, tipicamente, nelle figure dello [...] conosciuta da Paul D.G. du Bois-Reymond, 1831-1889, e da Dedekind) divenne, poi, uno dei principali strumenti della logica e dellateoriadellacalcolabilità nel corso del 20° secolo. Si dimostra che se A è l’insieme dei numeri reali x compresi tra 0 ...
Leggi Tutto