Cerca in:
Matematica: problemi aperti
Enciclopedia della Scienza e della Tecnica (2007)
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 macchina di Turing riconosce PRIMO se, dando come input una stringa, si ferma e la accetta soltanto se rappresenta un primo.
Con ...
Leggi Tutto
CATEGORIA:
TEMI GENERALI
Computazione, teoria della
Enciclopedia della Scienza e della Tecnica (2007)
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 macchina di Turing non deterministica (brevemente MTND) che, per lo stesso stato e lo stesso carattere letto sul nastro, può eseguire più ...
Leggi Tutto
CATEGORIA:
ANALISI MATEMATICA
Complessità algoritmica
Enciclopedia della Scienza e della Tecnica (2007)
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 macchina di Turing risolvente è deterministica. Tutte le funzioni f(n) citate nel seguito sono per ipotesi funzioni calcolabili, cioè per ogni n esiste ...
Leggi Tutto
CATEGORIA:
TEMI GENERALI
Penrose, Sir Roger
Enciclopedia on line
Matematico e fisico britannico (n. Colchester 1931). P. ha dato importanti contributi nella teoria della relatività generale, formulando l'ipotesi secondo la quale la singolarità centrale di un buco nero [...] su un'analogia tra le attività della mente e una macchina di Turing, accomunate dalla capacità di operare per algoritmi. Ha inoltre proposto e studiato la nozione di tassellazione quasi periodica del piano Tra le sue opere ricordiamo: Techniques ...
Leggi Tutto
CATEGORIA:
BIOGRAFIE
lambda
Enciclopedia on line
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 macchina di Turing. Molti linguaggi di programmazione funzionali, tra cui per es. il LISP ...
Leggi Tutto
CATEGORIA:
GRAMMATICA
–
TEMI GENERALI
–
ANTROPOLOGIA FISICA
–
MICROBIOLOGIA
–
FISICA MATEMATICA
–
FISICA NUCLEARE
–
LOGICA MATEMATICA
Böhm, Corrado
Enciclopedia on line
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 macchina di Turing è 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
CATEGORIA:
BIOGRAFIE
LOGICA E INFORMATICA
Enciclopedia Italiana - V Appendice (1993)
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 macchina di Turing. Successivamente sono stati formulati ...
Leggi Tutto
Informatica teorica
Enciclopedia della Scienza e della Tecnica (2007)
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 macchine di Turing. A tali studi hanno fatto seguito quelli di Manuel Blum e Albert Meyer, aventi per oggetto le proprietà astratte (indipendenti ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. L'analisi numerica
Storia della Scienza (2004)
La seconda rivoluzione scientifica: matematica e logica. L'analisi numerica
Paolo Zellini
L'analisi numerica
L'analisi numerica moderna comincia a delinearsi verso la metà del XX sec., con le prime [...] procedure aritmetiche. Per questo era opportuno introdurre modelli di calcolo il più possibile somiglianti alla macchina di Turing, sebbene calibrati sulla natura specifica del problema numerico. Prima di von Neumann fu Scholtz a introdurre, in una ...
Leggi Tutto
CATEGORIA:
STORIA DELLA MATEMATICA
Fondamenti della matematicae teoria algoritmica dell'informazione
Enciclopedia della Scienza e della Tecnica (2007)
Fondamenti della matematica e teoria algoritmica dell'informazione
Gregory J. Chaitin
Ciò che possiamo dimostrare intorno ai fondamenti della matematica usando i suoi stessi metodi costituisce la metamatematica, [...] realizzabili nel mondo fisico, per esempio da una macchina. Benché egli si avvalga di un linguaggio di programmazione estremamente primitivo (ora chiamato 'macchina di Turing'), si tratta ugualmente di un decisivo passo avanti verso l'era del ...
Leggi Tutto
CATEGORIA:
LOGICA MATEMATICA