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 [...]
L(M) è ricorsivo L(M) non è ricorsivo.
Per concludere accenniamo solo a due conseguenze che la teoria della decidibilità ha nell'ambito delle applicazioni. Sarebbe utile poter inserire un programma filtro all'ingresso di un calcolatore, per decidere ...
Leggi Tutto
lògica matemàtica Branca della logica, che utilizza un linguaggio simbolico e adotta un sistema di calcolo di tipo algebrico per esaminare le espressioni di un discorso deduttivo. Queste ultime possono [...] . Più o meno negli stessi anni Tarski pubblica i risultati ottenuti nei primi anni Trenta sulla completezza e decidibilità della teoria elementare dei numeri reali e mostra come trasferire queste proprietà alla geometria, formulando in termini logici ...
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 [...] delle relazioni del gruppo è ricorsivamente enumerabile, rendendo così esplicita l’analogia con i problemi di assiomatizzabilità e decidibilità per teorie. Su un altro versante si pone il teorema dimostrato da Yuri Matijasevic (1968), il quale prova ...
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. [...] dimostrò che la teoria degli interi con + come unico operatore è decidibile. Büchi ottenne negli anni Sessanta la decidibilità di un'altra porzione della logica: la teoria monadica del secondo ordine degli interi con successore. La dimostrazione si ...
Leggi Tutto
Dimostrazione, teoria della
Jean-Yves Girard
La teoria della dimostrazione nasce negli anni Venti del Novecento come strumento di realizzazione del programma di David Hilbert per la fondazione della [...] formule nei sequenti e quindi la proprietà della sottoformula ci permetterebbe di estendere anche al primo ordine la decidibilità che abbiamo nel caso enunciativo. Stesso discorso per le disgiunzioni di Herbrand, che sarebbero tutte di lunghezza ...
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 [...] teoria solleva un intenso dibattito in quanto si pone in antitesi con la spiegazione neodarwiniana del cambiamento evolutivo.
1968
Decidibilità della teoria dei campi finiti. L'americano James Ax dimostra che esiste un algoritmo per decidere se una ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1941-1950
1941-1950
1941
Le successioni esatte. Introdotte in una nota sui gruppi di coomologia (priva di dimostrazioni) dal polacco Witold Hurewicz ed estensivamente [...] poliedro e di complesso cellulare. Nello stesso anno riesce a costruire CW-complessi con preassegnati gruppi di omotopia.
Decidibilità della teoria delle algebre di Boole. Il logico polacco Alfred Tarski dimostra che la teoria delle algebre di Boole ...
Leggi Tutto
Il Contributo italiano alla storia del Pensiero: Scienze (2013)
La logica e i fondamenti della matematica tra Ottocento e Novecento
Mario Piazza
I fondamenti della geometria
Nella seconda metà dell’Ottocento, in tutta Europa il baricentro delle ricerche geometriche [...] che presenta gli assiomi per il calcolo dei predicati, rispetto al quale viene posta la questione della completezza e della decidibilità. L’epoca d’oro della logica era alle porte. Le rose stavano fiorendo, ma non in Italia, dove il giovane ...
Leggi Tutto
decidibilita
decidibilità s. f. [der. di decidibile]. – La qualità o la condizione di essere decidibile, sia in senso generico, sia nel sign. specifico della logica matematica.