complessità Caratteristica di un sistema (perciò detto complesso), concepito come un aggregato organico e strutturato di parti tra loro interagenti, in base alla quale il comportamento globale del sistema [...] rispetto alle dimensioni L del problema. Un problema è detto NP (che appartiene alla classe NP) se una macchinadiTuring non deterministica è in grado di risolverlo in tempo polinomiale. Dati ora due problemi R e Q si dice che «R si riduce a Q ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1961-1970
1961-1970
1961
Famiglia universale. Il giapponese Masatake Kuranishi mostra che esiste sempre un certo tipo di famiglia olomorfa di strutture complesse [...] tempo (o spazio) richiesta per risolvere il problema con una macchinadiTuring, in funzione della lunghezza dell'input. Essi dimostrano anche l'esistenza di molte coppie di funzioni f(n)⟨g(n) per cui esistono problemi risolubili in tempo g(n) ma non ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1951-1960
1951-1960
1951
Sui gruppi di omotopia e di omologia. In una serie di articoli (Homologie singulière des espaces fibrés) Jean-Pierre Serre fornisce [...] definiti da automi finiti sono detti regolari e formano una sottoclasse propria dei linguaggi riconoscibili da una macchinadiTuring.
Nasce l'algebra omologica. H. Cartan e S. Eilenberg pubblicano il trattato Homological algebra (completato fin dal ...
Leggi Tutto
Undicesima lettera dell’alfabeto greco (maiuscolo Λ, minuscolo λ), corrispondente alla consonante latina l.
biologia Fago l. Batteriofago che ha come ospite il batterio Escherichia coli. Su di esso sono [...] e anzi può essere usato per dare una definizione di computabilità di una funzione. In questo senso il l. calcolo è un modello di computazione equivalente alla macchinadiTuring. Molti linguaggi di programmazione funzionali, tra cui per es. il LISP ...
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 [...] spec. per misurazioni geodetiche. ◆ [ALG] Fibrato u.: v. fibrati: II 571 d. ◆ [ASF] Funzione u. (di luminosità): v. galassie: II 810 e. ◆ [INF] MacchinadiTuring u.: v. automi, teoria degli: I 330 e. ◆ [OTT] Obiettivo u.: nella tecnica fotografica ...
Leggi Tutto
macchinamàcchina [Der. del lat. machina, dal gr. machaná o mechané] [LSF] Dispositivo costituito da un complesso di parti collegate in modo da ottenere un certo scopo, che spesso è la produzione di [...] discreti del comportamento di m. o dispositivi automatici reali o realizzabili; in partic., m. diTuring (v. Gödel, teorema di: III 56 f , quali i trasformatori e i raddrizzatori: v. macchine elettriche (anche per i vari tipi particolari non nominati ...
Leggi Tutto
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
SINERGETICA
Fortunato Tito Arecchi
Definizione e storia del termine. - Il termine s. è stato introdotto da H. Haken per denotare la scienza dei sistemi composti di molti sottosistemi in mutua interazione. [...] con particolare riguardo a sistemi biologici. Nel 1952 A. Turing formulava la teoria generale della morfogenesi nei sistemi chimici. un processo di ordine che implica una riduzione di entropia. Sistemi di tal genere non sono macchinedi Carnot, ...
Leggi Tutto
La seconda rivoluzione scientifica: fisica e chimica. La Seconda guerra mondiale
Daniel J. Kevles
La Seconda guerra mondiale
La Seconda guerra mondiale vide un impiego senza precedenti della tecnologia. [...] L'unità dell'OSRD ideò tuttavia una spoletta che aveva la forma di un rozzo radar in miniatura e che innescava la bomba quando si ben presto, il matematico Alan M. Turing ideò una potentissima macchina per la decodificazione dalla quale, all'inizio ...
Leggi Tutto
macchina
màcchina (ant. màchina) s. f. [dal lat. machĭna, che è dal gr. dorico μαχανά, attico μηχανή]. – 1. In senso storico e antropologico, qualsiasi dispositivo o apparecchio costruito collegando opportunamente due o più elementi in modo...