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
trivalente
trivalènte [agg. Comp. di tri- e valente] [CHF] Di elemento chimico che ha valenza tre, cioè che presenta trivalenza. ◆ [ALG] [FAF] Logica t.: quella nella quale si ammette che una proposizione [...] possa essere o vera o falsa o indecidibile. ...
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 [...] di questi risultati è il teorema di Gödel (1931), il quale afferma che l’aritmetica di Peano del primo ordine è indecidibile. Il risultato si può estendere a teorie molto più deboli dell’aritmetica di Peano – quale il sistema Q di Robinson – e ...
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, [...] R, la cui complessità è superiore a quella del sistema del computer. Una domanda come
"R è una sequenza casuale?"
è indecidibile per il computer. La complessità delle proposizioni "R è casuale" e "R non è casuale" è troppo grande per essere tradotta ...
Leggi Tutto
risolubile
risolùbile [agg. Der. del lat. resolubilis "che si può risolvere", dal part. pass. resolutus del lat. resolvere "sciogliere di nuovo"] [ALG] Equazione algebrica r. per radicali, o r. algebricamente: [...] di Ising in una e due dimensioni (v. modelli risolubili in meccanica statistica). ◆ [ALG] [FAF] Problema non r., o indecidibile: nella logica matematica, problema logico che in linea di principio non ammette una soluzione generale: è tale, per es ...
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. [...] . In modo equivalente, L è computabile se è riconosciuto da una macchina di Turing che si ferma sempre. Un tipico linguaggio indecidibile è l'insieme delle coppie (⟨M⟩, x), dove M è una macchina di Turing, opportunamente codificata da una parola, e x ...
Leggi Tutto
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 [...] , a meno che non sia banalmente verificata da tutti o da nessuno.
Corollario. Per un'arbitraria MT M le seguenti questioni sono indecidibili:
L(M)=Φ L(M)≠Φ,
L(M) è finito L(M) Σ*,
L(M) è regolare L(M) è libero,
L(M) è ricorsivo L(M) non è ricorsivo ...
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 [...] del campo razionale. La matematica americana Julia Robinson dimostra che la teoria del primo ordine del campo razionale è indecidibile; non esiste, cioè, un algoritmo che, data una formula della logica del primo ordine nel linguaggio della teoria dei ...
Leggi Tutto
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, [...] algoritmi esponenziali conforta la congettura che P≠NP, ma la prova che tale affermazione sia vera o falsa, decidibile o indecidibile non sembra vicina.
La scoperta che Psod è NP-completo ha permesso di dimostrare che altri problemi P∈NP hanno questa ...
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 [...] è spiegata da una diversa interpretazione del terzo valore. Per Kleene 1/2 significa indecidibile (si applica quindi alle proposizioni indecidibili dell'aritmetica), mentre 1/2 per Bochvar significa paradossale e si applica quindi alle proposizioni ...
Leggi Tutto
indecidibile
indecidìbile agg. [der. di decidere, col pref. in-2]. – Propr., che non può essere deciso. In logica, è detto di ogni asserzione, proposizione, formula per la quale si dimostra che, in un dato sistema formalizzato, né essa né...
indecidibilita
indecidibilità s. f. [der. di indecidibile]. – L’essere indecidibile. In logica, condizione nella quale è impossibile decidere se una proposizione è vera o falsa.