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
Allen, Frances E.
Allen, Frances. – Informatica statunitense (n. New York 1932). Nel 2006 ha ricevuto il premio Turing dell’ACM (Association for computing machinery), il primo assegnato a una donna, [...] per i suoi contributi pionieristici alla teoria e alla pratica delle tecniche di ottimizzazione che forniscono i fondamenti per i moderni compilatori ottimizzanti e parallelizzanti. Laureatasi in matematica ...
Leggi Tutto
transputer
Lorenzo Seno
Particolare tipo di microprocessore. I calcolatori elettronici, implementazioni materiali e finite delle macchine di Turing, nascono come macchine di calcolo sequenziali, nelle [...] quali viene cioè eseguita una sola operazione alla volta, e qualunque problema di elaborazione deve venire ridotto a una successione di operazioni consecutive. Fin dai primi tempi dell’elaborazione elettronica ...
Leggi Tutto
Thacker, Charles P.
Thacker, Charles P. – Fisico statunitense (n. Pasadena, CA, 1943). Nel 2009 ha ricevuto il premio Turing dell’ACM (Association for computing machinery) per i contributi forniti nel [...] campo del design e della costruzione del computer, in particolare per la progettazione e realizzazione pionieristica di apparati prototipi dei PC moderni e dei tablet, e per gli apporti alla nascita della ...
Leggi Tutto
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
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] 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à 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
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
Valiant
Valiant Leslie Gabriel (Budapest 1949) teorico dell’informatica inglese. Di madre ungherese, si trasferì ben presto in Inghilterra, dove frequentò il King’s College di Cambridge e l’Imperial [...] artificiale. È membro della Royal Society di Londra e della National Academy of Sciences (usa). Nel 1986 ha ricevuto il Premio Nevanlinna e nel 2010 il premio Turing per i suoi fondamentali contributi nel campo dell’intelligenza artificiale. ...
Leggi Tutto
pensante
pensante [Der. del part. pres. pensans -antis del lat. pensare "esercitare l'attività del pensiero"] [INF] Macchina p.: secondo la definizione originale di M.A. Turing (1950), macchina in grado [...] di ricevere delle domande e di elaborare delle risposte simili a quelle che potrebbe fornire una persona nelle stesse circostanze e in modo che la persona che interroga non possa distinguere in alcun modo ...
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...