Turing Alan Mathison
Dizionario delle Scienze Fisiche (1996)
Turing 〈tiùrin〉 Alan Mathison [STF] (Londra 1912 - Wilmslow, Cheshire, 1954) Lettore di matematica nell'univ. di Manchester (1948). ◆ [INF] Ipotesi di T.: v. automi, teoria degli: I 330 b. ◆ [INF] Macchina [...] di T.: modello meccanico di algoritmi, proposto da T. nel 1936: v. automi, teoria degli: I 330 b e Gödel, teorema di: III 56 f. ◆ [INF] Test di T.: v. intelligenza artificiale: III 233 b ...
Leggi Tutto
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
transputer
Enciclopedia della Scienza e della Tecnica (2008)
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
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
Automi e linguaggi formali
Enciclopedia della Scienza e della Tecnica (2007)
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
CATEGORIA:
TEMI GENERALI
informatica
Enciclopedia on line
Scienza che studia l’elaborazione delle informazioni e le sue applicazioni; più precisamente l’i. si occupa della rappresentazione, dell’organizzazione e del trattamento automatico della informazione. [...] nuovo elaboratore fu inaugurato nel 1952. A seguito delle ricerche sulla ricorsività e sulla macchina ideale condotte da Turing, von Neumann aveva maturato la convinzione che quel computer dovesse essere considerato non solo come ‘macchina da calcolo ...
Leggi Tutto
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
pensante
Dizionario delle Scienze Fisiche (1996)
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
CATEGORIA:
TEMI GENERALI
Ritchie, Dennis M.
Enciclopedia on line
Programmatore informatico statunitense (New York 1941 - Berkeley Heights, New Jersey, 2011). È noto soprattutto per aver creato, in collaborazione con K. Thompson, il sistema operativo UNIX, per il quale [...] hanno ricevuto entrambi il Premio Turing nel 1983. Inoltre, insieme a B. Kernighan, è considerato l’inventore del linguaggio di programmazione C. ...
Leggi Tutto
CATEGORIA:
BIOGRAFIE