Turing, Alan Mathison
Enciclopedia on line
Matematico e logico matematico britannico (Londra 1912 - Wilmslow, Cheshire, 1954). Pioniere della scienza dell'informazione e dell'intelligenza artificiale, ha legato il suo nome, in particolare, a un metodo da lui indicato per dare un significato preciso al concetto intuitivo di funzione effettivamente computabile mediante una macchina astrattamente definita (macchina di T.).
Dal 1948 fu lettore ...
Leggi Tutto
CATEGORIA:
BIOGRAFIE
macchina di Turing
Enciclopedia della Scienza e della Tecnica (2008)
Macchina di Turing
Mauro Cappelli
Modello di agente di calcolo adatto a simulare la logica di qualsiasi algoritmo computazionale. La macchina formale fu proposta nel 1936 dal logico e matematico britannico [...] di rendere automatica una macchina da scrivere). Oggi ne esistono molte varianti, la più semplice delle quali è la macchina di Turing a nastro, formata da un’unità di controllo contenente un programma con un numero finito di istruzioni, da un nastro ...
Leggi Tutto
Complessità algoritmica
Enciclopedia della Scienza e della Tecnica (2007)
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, [...] )=1. Le complessità in spazio e tempo S(n) e T(n) per M e P si definiscono esattamente come per le macchine di Turing ordinarie impiegando i nuovi valori di s(α) e t(α) e le corrispondenti classi di complessità dei problemi si indicano con NDSPAZIO(S ...
Leggi Tutto
CATEGORIA:
TEMI GENERALI
La grande scienza. Automi e linguaggi formali
Storia della Scienza (2003)
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] e il numero dei passi è limitato da un polinomio. Un linguaggio L è in IP (interattivo polinomiale) se esiste una macchina di Turing probabilistica V (il Verificatore) che lavora in tempo polinomiale e tale che x∈L se e solo se esiste una macchina di ...
Leggi Tutto
computabilità
Enciclopedia on line
computabilità In logica matematica, nozione che di solito s’identifica con quella di ricorsività generale, introdotta intorno al 1936 da A.M. Turing e da E.L. Post. Una funzione numerica di n variabili [...] si dice computabile se esiste un algoritmo per cui si possa, con un numero finito di passi, calcolare per ogni ennupla di argomenti il valore assunto dalla funzione ...
Leggi Tutto
CATEGORIA:
LOGICA MATEMATICA
Calcolo
Enciclopedia Italiana - VII Appendice (2006)
Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori [...] non è affatto soggetto a tali limitazioni. Fu soltanto nel 1985, però, che si arrivò alla prima definizione di macchina di Turing quantistica, grazie al lavoro di D. Deutsch, che riuscì così a gettare le basi teoriche del c. quantistico.
Uno dei ...
Leggi Tutto
CATEGORIA:
TEMI GENERALI
calcolabilita
Enciclopedia della Scienza e della Tecnica (2008)
calcolabilità
Fabrizio Luccio
La teoria che studia la possibilità di calcolare una funzione dagli interi sugli interi mediante un modello astratto di computazione come per es. la macchina di Turing. [...] alcun algoritmo di calcolo, ovvero problemi non risolubili mediante algoritmi. Il primo di questi problemi, scoperto da Alan Turing nel 1936, può essere formulato in termini intuitivi affermando che non esiste algoritmo che, presi come dati d ...
Leggi Tutto
CATEGORIA:
LOGICA
Chaitin, Gregory
Enciclopedia on line
Matematico statunitense (New York 1947). Ha apportato importanti contributi alla teoria algoritmica dell'informazione (AIT), combinando il metodo di C. Shannon (') e la teoria della computabilità di A.M. [...] Turing ('). Autore di molti saggi, i suoi studi hanno portato a dimostrare l'esistenza della casualità anche in aritmetica. ...
Leggi Tutto
CATEGORIA:
BIOGRAFIE
Fondamenti della matematicae teoria algoritmica dell'informazione
Enciclopedia della Scienza e della Tecnica (2007)
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
CATEGORIA:
LOGICA MATEMATICA
Böhm, Corrado
Enciclopedia on line
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
CATEGORIA:
BIOGRAFIE