Fondamenti della matematica e teoria algoritmica dell'informazione
Gregory J. Chaitin
Ciò che possiamo dimostrare intorno ai fondamenti della matematica usando i suoi stessi metodi costituisce la metamatematica, [...] , usato in teoria degli insiemi, che egli applica all'elenco di tutti i numeri reali calcolabili. In tal modo Turing ottiene un numero reale non calcolabile R, come spiegheremo oltre, e una fonte di incompletezza totalmente diversa da quella scoperta ...
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 [...] a quella di ricorsività e di λ-definibilità, ma calcolabile da una macchina astratta di un certo tipo.
Una macchina di Turing (MT) consiste in un insieme finito di stati e in un nastro monodimensionale finito, ma potenzialmente illimitato in entrambe ...
Leggi Tutto
automa a programma
automa a programma automa universale che opera secondo un programma di calcolo, cioè secondo una successione di istruzioni espresse in un linguaggio di programmazione. Il suo operare, [...] stato finale (risultato del calcolo). Esso è perciò caratterizzato da:
• una memoria analoga al nastro della macchina di Turing; alcune parti della sua memoria sono però individuabili con un «nome» e sono dette registri, ognuno dei quali contiene ...
Leggi Tutto
problema dell’arresto
Fabrizio Luccio
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problema dell’arresto nacque nel 1936, sulla base di studi sugli [...] arbitrariamente un algoritmo A e un dato D, stabilire se la computazione A(D) termina in un numero finito di passi. Turing dimostrò che non può esistere alcun algoritmo ARR che stabilisca in tempo finito se la computazione A(D) si arresta anch’essa ...
Leggi Tutto
Considerazioni metodologiche sullo studio delle funzioni cerebrali
Frank van der Velde
(Unit of Experimental and Theoretical Psychology, Leiden Universiteit, Leida, Paesi Bassi)
L'integrazione tra neuroscienze [...] , e riguarda la differenza tra i cosiddetti automi a stati finiti (ASF) e le macchine come la macchina di Turing. Una macchina di Turing consiste in un ASF connesso a una memoria di lavoro che elabora l'informazione di utilità immediata.
Un ASF è ...
Leggi Tutto
Markov, algoritmo di
Markov, algoritmo di sistema di riscrittura di stringhe costruito sulla base di una lista di regole. Gli algoritmi di Markov possono rappresentare ogni espressione matematica calcolabile [...] e sono quindi un modello generale di calcolo (si usa dire che è un sistema Turing completo, nel senso che ogni funzione Turing-calcolabile è rappresentabile in questo simbolismo). Essi sono costituiti da un insieme di regole di riscrittura della ...
Leggi Tutto
Böhm, Corrado. – Matematico e informatico italiano (Milano 1923 - Roma 2017). Laureatosi nel 1946 in ingegneria elettronica presso il Politecnico di Losanna, ha conseguito il dottorato in matematica al [...] Politecnico di Zurigo nel 1951. Dalle sue ricerche sui linguaggi per la programmazione sulla macchina di Turing è nato, in collaborazione con G. Jacopini, il teorema di Böhm-Jacopini (1966). Tra i suoi contributi più importanti vi è il cosiddetto ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. L'analisi numerica
Paolo Zellini
L'analisi numerica
L'analisi numerica moderna comincia a delinearsi verso la metà del XX sec., con le prime [...] il prodotto delle norme (di Frobenius) di A e di A−1, cioè μ(A)=∥A∥∙∥A−1∥, in un importante articolo di Turing, Rounding-off errors in matrix processes (1948), poco dopo il contributo di von Neumann e Goldstine. In norma euclidea lo stesso prodotto è ...
Leggi Tutto
Rejewski
Rejewski Marian Adam (Bydgoszcz 1905 - Varsavia 1980) matematico polacco. Decrittò per primo (1932) la chiave logica dei messaggi tedeschi criptati con la macchina Enigma. I suoi studi vennero [...] portati avanti negli anni della seconda guerra mondiale con il contributo di A.M. Turing e permisero ai servizi di intelligence inglese di decifrare un grande numero di messaggi dello stato maggiore tedesco. Rifugiatosi in Gran Bretagna nel 1942, ...
Leggi Tutto
Sifakis, Joseph
Sifakis, Joseph. ‒ Informatico greco, naturalizzato francese (n. Heraklion, Creta, 1946). Direttore di ricerca presso il CNRS (Centre national de la recherche scientifique) e fondatore [...] laboratory di Grenoble. Nel 2007 è stato insignito – insieme a E. Allen Emerson ed Edmund Clarke – del premio Turing dell'ACM (Association for computing machinery) per i lavori sul model checking, una tecnica di controllo utilizzata nell’ambito ...
Leggi Tutto
turingiano
agg. e s. m. [dal nome della regione della Turingia (v. turingio)]. – Piano geologico superiore del permiano, tipico dell’Europa centro-orientale e in partic. della Turingia (corrispondente alla facies detta in Germania Zechstein),...
turingio
turìngio agg. [der. del nome della regione] (pl. f. -ge o -gie). – Della Turingia (ted. Thüringen), regione storica e moderna della Germania centro-orientale: le antiche popolazioni t., di stirpe germanica (e, sost., i turingi); il...