MacchinadiTuring
Mauro Cappelli
Modello di agente di calcolo adatto a simulare la logica di qualsiasi algoritmo computazionale. La macchina formale fu proposta nel 1936 dal logico e matematico britannico [...] nei due versi e risulta diviso in celle, ciascuna contenente un simbolo appartenente a un insieme finito di simboli detto alfabeto.
Ogni ;macchinadiTuring deve possedere un alfabeto che contenga il simbolo speciale b (blank, spazio), i simboli 0 e ...
Leggi Tutto
Matematica
Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo [...] state dimostrate equivalenti. È possibile costruire delle macchinediTuring che calcolano una qualsiasi funzione ricorsiva, dei sistemi di Post che eseguono il calcolo di una qualsiasi macchinadiTuring ecc. Questo è una conferma empirica della ...
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
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
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
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
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...