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
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, [...] .
Un altro modello astratto frequentemente utilizzato negli studi di complessità computazionale è la macchinadiTuring. Tale macchina dispone di una memoria interna con un numero finito di stati e di un nastro (memoria esterna) suddiviso in celle, e ...
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 [...] nastro di una macchinadiTuring e la memoria di un elaboratore elettronico, e tra le regole scritte sul nastro di una macchinadiTuring e i programmi memorizzati nella memoria di un elaboratore elettronico.
È evidente che la macchinadiTuring si ...
Leggi Tutto
L'Universo matematico
John D. Barrow
(Astronomy Centre, University of Sussex, Brighton, Gran Bretagna)
Parte di questo saggio è stata pubblicata sotto il titolo Perché il mondo è matematico? Roma-Bari, [...] computer reale possegga maggiore abilità nel risolvere problemi.
Le operazioni matematiche che non possono essere calcolate da una macchinadiTuring sono dette non computabili. Ne sono noti molti esempi, la cui esistenza genera molti problemi fisici ...
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 [...] : nel primo caso avevamo automi finiti ed espressioni razionali, nel secondo automi a pila e grammatiche.
MacchinediTuring
Una macchinadiTuring opera mediante una memoria infinita (in realtà è sufficiente una parola su un alfabeto fissato, detto ...
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 [...] numero scritto in forma binaria e il linguaggio PRIMO è formato da tutte le stringhe che rappresentano numeri primi. Una macchinadiTuring riconosce PRIMO se, dando come input una stringa, si ferma e la accetta soltanto se rappresenta un primo.
Con ...
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, [...] minore o uguale S(n) e complessità in tempo minore o uguale T(n), dove l'iniziale D indica che la macchinadiTuring risolvente è deterministica. Tutte le funzioni f(n) citate nel seguito sono per ipotesi funzioni calcolabili, cioè per ogni n esiste ...
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
Tecnologie per la gestione dell’informazione
Francesco Rogo
Era digitale e società dell’informazione
L’informazione ha ormai conquistato i più diversi ambiti della nostra società, ricoprendo ruoli d’importanza [...] sui processi classici della computazione – basata sul modello astratto della macchinadiTuring –, bensì su un nuovo paradigma computazionale che altera la nozione di trattabilità della grandezza maneggiata dai computer, appunto l’informazione ...
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
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...