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
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
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
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
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
Metodo
GGerard Radnitzky
di Gerard Radnitzky
Metodo
sommario: 1. Introduzione. 2. Concetto e definizione di procedimento metodico, metodo e metodologia. a) Distinzione tra i vari livelli. b) Definizione [...] a porre certi limiti alle tecnologie: ad esempio dalla teoria matematica (dal teorema di Gödel) consegue che la costruzione di una macchinadiTuring capace di calcolare qualsiasi funzione è logicamente impossibile. Da teorie scientifiche consegue l ...
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
Logica matematica
Abraham Robinson
*La voce enciclopedica Logica matematica è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un’introduzione di Gabriele Lolli e un saggio di Beppo [...] Sembra ormai provato che la stessa nozione astratta dimacchinadiTuring abbia notevolmente contribuito allo sviluppo concreto dell'invenzione del calcolatore. Una macchinadiTuring - che prende il nome da A. M. Turing, che la ideò nel 1936 - è in ...
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
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
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...