Computazione, teoria della
Fabrizio Luccio
La necessità del calcolo, pur riconosciuta dall'uomo in tutte le epoche storiche, ha condotto solo in tempi relativamente recenti a una sistemazione teorica [...] accettate da X. Allora esiste una MT Y che accetta L.
Anche nel caso presente è significativo definire una macchinadiTuring non deterministica (brevemente MTND) che, per lo stesso stato e lo stesso carattere letto sul nastro, può eseguire più ...
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
La seconda rivoluzione scientifica: matematica e logica. Teoria della ricorsivita
Piergiorgio Odifreddi
Teoria della ricorsività
La teoria della ricorsività affronta lo studio delle funzioni con lo [...] .
Fra le varie definizioni equivalenti di funzione ricorsiva abbiamo citato la nozione di calcolabilità mediante macchine astratte. Tale approccio è dovuto a Turing e Post, e le cosiddette 'macchinediTuring' si possono oggi facilmente descrivere ...
Leggi Tutto
teoremi di indecidibilità
Silvio Bozzi
In logica matematica, risultati che affermano che una data teoria formalizzata T non è decidibile, vale a dire non ammette un algoritmo in grado di stabilire in [...] , per es., il problema della fermata per macchinediTuring, il problema della lambda-convertibilità o quello della derivabilità di parole entro sistemi di Post e così via. Di fatto questi problemi risultano intertraducibili con questioni sull ...
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
transputer
Lorenzo Seno
Particolare tipo di microprocessore. I calcolatori elettronici, implementazioni materiali e finite delle macchinediTuring, nascono come macchinedi calcolo sequenziali, nelle [...] quale un esempio è rappresentato dai CUBE computer, con topologia ipercubica), vede decine, centinaia o migliaia di CPU cooperare alla soluzione di un problema complesso segmentato in molti compiti più semplici. Lo sviluppo del software (e della rete ...
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
TuringTuring Alan Mathison (Londra 1912 - Wilmslow, Cheshire, 1954) logico e matematico inglese. È uno dei fondatori della teoria della → calcolabilità e quindi dell’informatica, e un pioniere dell’intelligenza [...] a partire dalle più elementari operazioni del calcolo, descrive quella che poi sarà detta macchinadi → Turing. In quello stesso periodo entrò in contatto con A. Church, che lavorava sugli stessi temi relativi alla calcolabilità e alla decidibilità ...
Leggi Tutto
intelligènza artificiale (IA) Disciplina che studia se e in che modo si possano riprodurre i processi mentali più complessi mediante l'uso di un computer. Tale ricerca si sviluppa secondo due percorsi [...] a oggi, però, nessun calcolatore è mai riuscito a superare il test diTuring (che prende il nome dal logico A.M. Turing che lo ideò) che afferma che una macchina 'pensa' quando un osservatore umano che interagisca con essa attraverso una tastiera ...
Leggi Tutto
(o computer, o elaboratore elettronico) Apparecchio o dispositivo utilizzato per l’elaborazione di dati e segnali.
Cenni storici
Le origini
Il desiderio di realizzare uno strumento in grado di compiere [...] E.L. Post, i quali in modo indipendente introdussero nel 1936 due modelli concettuali di elaborazione: la macchinadiTuring e il sistema di Post.
I prototipi
I c. progettati e prodotti tra il 1936 e il 1950 erano essenzialmente prototipi, costruiti ...
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...