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
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
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
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
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
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, [...] concettuali, da un lato, i primi modelli astratti sviluppati dai logici negli anni Trenta e Quaranta (il modello proposto da Turing, fondato sul concetto di transizione di stato, e quello funzionale sviluppato da A. Church e S.C. Kleene) e, dall ...
Leggi Tutto
Matematica: problemi aperti
Claudio Procesi
Prima di parlare dei problemi aperti nella matematica è bene riflettere su quelli che ne hanno segnato la storia passata. Sono infatti proprio questi che [...] lingue parlate e sono in genere insiemi infiniti di parole. L'idea di algoritmo viene così trasformata in quella di macchina di Turing che riconosce un dato linguaggio L, ovvero una macchina che accetta l'input, lo elabora con una serie di passi e si ...
Leggi Tutto
Stabilità
Corrado Mascia
Uno degli aspetti fondamentali del mondo naturale è la sua potenzialità di trasformazione; è proprio l'evolvere degli oggetti che permette all'uomo di percepire lo scorrere [...] a un'altra (stabile). Nell'ambito dell'instabilità rientrano due meccanismi particolarmente interessanti: il caos e l'instabilità di Turing.
Le basi per una definizione rigorosa del caos sono state poste dal matematico francese H. Poincaré. Uno degli ...
Leggi Tutto
La vita artificiale
Thomas S. Ray
(ATR Human lnformation Processing, Research Laboratories Kyoto, Giappone)
La vita artificiale (VA) estende il campo di indagine della biologia, permettendo di studiare [...] ridicolo pensare che una macchina intelligente possa essere del tutto indistinguibile da un uomo (in teoria il test di Turing dovrebbe essere in grado anche di distinguere esseri umani con una diversa formazione culturale). Ritengo che una forma di ...
Leggi Tutto
universale
universale [agg. e s.m. Der. del lat. universalis, da universus "tutto intero"] [FTC] Qualifica di dispositivi o apparecchi che: (a) possono essere usati in condizioni diverse di alimentazione [...] ] Fibrato u.: v. fibrati: II 571 d. ◆ [ASF] Funzione u. (di luminosità): v. galassie: II 810 e. ◆ [INF] Macchina di Turing u.: v. automi, teoria degli: I 330 e. ◆ [OTT] Obiettivo u.: nella tecnica fotografica, obiettivo dotato di un attacco che gli ...
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...