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
sistema formale
Sistema costituito da un linguaggio formale e un apparato deduttivo. Un esempio di s. f. è quello K per la logica proposizionale classica dato dalla coppia (LK; DK) dove LK è il linguaggio [...] detta metateoria, dimostrando teoremi riguardanti la sintassi e la semantica della teoria oggetto. Proprietà metamatematiche molto importanti da dimostrare per i s. f. sono, per es., la correttezza, la completezza, la coerenza e la decidibilità. ...
Leggi Tutto
funzione calcolabile
funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] è calcolabile: nel 1970, il matematico russo J. Matijasevič ha, infatti, dimostrato che il problema è indecidibile (→ decidibilità). L’esistenza di funzioni non calcolabili, come quella appena descritta, determina l’esigenza di capire quante e quali ...
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
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] dimostrò che la teoria degli interi con + come unico operatore è decidibile. Büchi dimostrò 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
Maria Francesca Ghirga
Abstract
Viene trattato il tema dell’interesse ad agire quale requisito della domanda giudiziale previsto dall’art. 100 del c.p.c. e implicato dal bisogno di tutela che condiziona [...] ancora difesa da Liebman (op. cit., 146 ss.), oggi si tende a collocare sul loro stesso piano, come condizioni di decidibilità della causa di merito (Consolo, C., op. cit., 531 ss.). Essi vanno accertati in giudizio preliminarmente all’esame del ...
Leggi Tutto
intuizionismo
intuizionismo concezione della matematica secondo cui l’affermazione di esistenza di enti matematici è lecita solo se si dispone di un metodo che ne garantisca la costruibilità. In questo [...] positivamente a indirizzare verso la ricerca di metodi dimostrativi costruttivi e quindi verso problemi quali quelli della decidibilità e della calcolabilità, che hanno caratterizzato la logica e la matematica del xx secolo, anche in connessione ...
Leggi Tutto
sistema formale
sistema formale apparato simbolico mediante il quale è possibile rappresentare formalmente i procedimenti logico-deduttivi delle dimostrazioni matematiche. Esempi di sistemi formali sono [...] dimostrabili una formula e la sua negazione). Ulteriori problemi riguardanti i sistemi formali sono l’→ indipendenza e la → decidibilità: la prima vale quando nessuno degli assiomi è dimostrabile a partire dagli altri, la seconda quando esiste un ...
Leggi Tutto
Medicina
Nicola Dioguardi e Riccardo de Sanctis
La medicina è la scienza che ha per oggetto lo studio delle malattie, la loro cura e prevenzione. Pratiche terapeutiche e sistemi che riguardano la salute [...] : 1) quando la decisione da prendere solleva dubbi di ordine religioso; 2) quando si deve esprimere un giudizio sulla decidibilità di fatti che vanno al di là dei paradigmi, delle regole, dei metodi accettati dalla medicina ufficiale e, più in ...
Leggi Tutto
automa
automa dispositivo in grado di effettuare una particolare azione in risposta a stimoli esterni. I computer sono esempi di automi complessi che, a partire da dati e programmi, eseguono i comandi. [...] non deterministici.
Automi più complessi riconoscono classi di linguaggi più ampie; tuttavia, aumentando la complessità diminuisce la decidibilità dei problemi che si definiscono su essi. Così, mentre i linguaggi regolari sono poco descrittivi, ma è ...
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.