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. [...] -free: nel primo caso avevamo automi finiti ed espressioni razionali, nel secondo automi a pila e grammatiche.
MacchinediTuring
Una macchinadiTuring opera con una memoria infinita (in realtà è sufficiente una parola su un alfabeto fissato, detto ...
Leggi Tutto
La grande scienza. Intelligenza artificiale
Marco Somalvico
Francesco Amigoni
Viola Schiaffonati
Intelligenza artificiale
In questa trattazione viene presentata l'intelligenza artificiale (nel seguito [...] dimacchina universale diTuring, una macchina concettuale in grado di trovarsi in un numero finito di stati diversi e di eseguire un numero limitato di azioni, al fine di poter esprimere qualsiasi tipo di procedura definita.
La macchinadiTuring ...
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
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
Böhm, Corrado. – Matematico e informatico italiano (Milano 1923 - Roma 2017). Laureatosi nel 1946 in ingegneria elettronica presso il Politecnico di Losanna, ha conseguito il dottorato in matematica al [...] nel 1951. Dalle sue ricerche sui linguaggi per la programmazione sulla macchinadiTuring è nato, in collaborazione con G. Jacopini, il teorema di Böhm-Jacopini (1966). Tra i suoi contributi più importanti vi è il cosiddetto teorema della separazione ...
Leggi Tutto
Scienza cognitiva
Antonio Rainone
Con la locuzione scienza cognitiva, dalla fine degli anni Settanta, si è soliti designare l'insieme delle discipline che hanno per oggetto lo studio dei processi cognitivi [...] possono essere individuati già nel celebre test escogitato da A. Turing (1950), il matematico che negli anni Trenta aveva teorizzato una macchinadi calcolo universale (macchinadiTuring) che sarebbe stata alla base della scienza dei calcolatori; a ...
Leggi Tutto
LOGICA E INFORMATICA
Carlo Cellucci
I. McCarthy (1963) afferma che è ragionevole sperare che le relazioni tra l'i. e la l. matematica nel prossimo secolo saranno altrettanto fruttuose di quelle tra [...] 1937). Per ottenere tale risultato Turing ideò un modello puramente matematico dei procedimenti di computo sotto forma di una macchina ideale capace di manipolare simboli, comunemente nota come macchinadiTuring. Successivamente sono stati formulati ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] Stearns e Philip M. Lewis, i quali hanno definito e studiato il concetto di classe di complessità per le macchinediTuring. A tali studi hanno fatto seguito quelli di Manuel Blum e Albert Meyer, aventi per oggetto le proprietà astratte (indipendenti ...
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
automa cellulare
Mauro Cappelli
Modello per lo studio dell’evoluzione di sistemi complessi, introdotto negli anni Cinquanta del secolo scorso, da John von Neumann e Stanislaw Ulam. Un automa cellulare [...] biologia. Ma le possibili applicazioni sono pressoché infinite: si pensi che alcuni automi cellulari, cosiddetti universali, sono in grado di simulare il comportamento di ogni altro automa cellulare o macchinadiTuring.
→ Self-organized criticality ...
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...