indecidibileindecidìbile [Comp. di in- neg. e decidibile "che non può essere deciso"] [ALG] [FAF] Teoria i.: quella per la quale non esiste nessun algoritmo mediante il quale sia possibile decidere [...] in un numero finito di passi, per ogni proposizione formulabile in essa, se sia vera o falsa; è tale, per es., l'intera aritmetica (v. Gödel, teorema di: III 53 c) ...
Leggi Tutto
Fondazionalismo e antifondazionalismo
Aldo Giorgio Gargani
Lungo linee direttrici che attraversano tanto la filosofia analitica e postanalitica, quanto quella di ispirazione ermeneutica (o filosofia [...] . Il punto decisivo del dibattito, sul quale fa perno la disamina critica di Dummett, è costituito dal problema degli enunciatiindecidibili, per i quali non sussistono prove o verifiche e che sono pertanto sprovvisti di un valore di verità secondo ...
Leggi Tutto
indecidibilita
indecidibilità in logica, termine utilizzato per indicare la non → decidibilità di una data proprietà. In particolare, un insieme è indecidibile se non esiste un algoritmo in grado di [...] di → Zermelo-Fraenkel. È importante distinguere il concetto di teoria indecidibile dalla nozione di formula indecidibile (→ decidibilità). Un esempio di enunciatoindecidibile è quello espresso nel decimo problema di Hilbert, relativo alle equazioni ...
Leggi Tutto
Informatica
Fabrizio Luccio
Franco P. Preparata
Carl-Erik Fröberg
Piero Sguazzero
Piero Dell'Orco e Tomaso Poggio
Teoria della computazione di Fabrizio Luccio
SOMMARIO: 1. Origine e motivazioni. [...] per P. Se L non è ricorsivo il problema è ‛indecidibile' e non ammette algoritmo di risoluzione; tra tali problemi è di'. Allora la formula M(2, 3) e la formula M(3, 2) sono enunciati (il primo falso, perché 2 non è maggiore di 3, e il secondo vero), ...
Leggi Tutto
STORIA DELLA MATEMATICA
Luigi Borzacchini
STORIA DELLA MATEMATICA
Il tempo della scienza senza tempo
La matematica è la più antica e la più immutabile delle discipline. Si può dire che la matematica [...] quali era il paradosso del mentitore: «io sto mentendo». Se questo enunciato è vero vuol dire che è falso, ma se è falso allora decidere se una formula aritmetica è vera è indecidibile). Gli stessi teoremi di incompletezza ammettevano una maggiore ...
Leggi Tutto
Algebra
Irving Kaplansky
sommario: 1. Introduzione. 2. Gruppi in generale. 3. Gruppi semplici finiti. 4. Gruppi infiniti. 5. Gruppi liberi. 6. Gruppi abeliani infiniti. 7. Anelli in generale. 8. Corpi. [...] un gruppo libero è libero. Sotto ipotesi di finitezza si può migliorare l'enunciato dicendo che, se G è libero con n generatori ed H è un matematica odierna, questo problema è assolutamente indecidibile.
Le consuete definizioni di estremo superiore ...
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 [...] risultati si fa largo uso della condizione di compattezza di Palais-Smale enunciata tre anni prima.
Teoremi di punto fisso. M.F. Atiyah e calcolo a meno di catene finite di semplificazioni è indecidibile. Scott trova un modello del λ-calcolo che ...
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. [...] da una macchina di Turing che si ferma sempre. Un tipico linguaggio indecidibile è l'insieme delle coppie (⟨M⟩, x), dove M è , il 'Dimostratore' e il 'Verificatore'; l'input è un enunciato da dimostrare. Le due macchine comunicano a ogni passo e il ...
Leggi Tutto
Logiche non standard
Claudio Pizzi
Alcune famiglie di logiche non standard sono costituite da logiche che sono estensioni assiomatiche di quella standard, mentre altre constano di logiche rappresentabili [...] 'analisi dei condizionali controfattuali. Per esempio, la forma dell'enunciato 'se il naso di Cleopatra fosse stato più lungo Roma Per Kleene 1/2 significa indecidibile (si applica quindi alle proposizioni indecidibili dell'aritmetica), mentre 1/2 ...
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 [...] una macchina di Turing che si ferma sempre. Un tipico linguaggio indecidibile è l'insieme delle coppie (〈M〉, x), dove M è , il dimostratore e il verificatore, e l'ingresso è un enunciato da dimostrare. Le due macchine comunicano a ogni passo e il ...
Leggi Tutto
risolubile
risolùbile (ant. resolùbile) agg. [der. di risolvere; cfr. lat. tardo resolubĭlis «che si può nuovamente sciogliere»]. – Che si può risolvere: dubbio, problema r.; sciarada facilmente risolubile. In partic.: 1. In diritto privato,...