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
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 [...] 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
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
Ambiguità
Alessandro Cappabianca
Nel suo studio sull'a. nel linguaggio poetico (Seven types of ambiguity), la cui prima edizione risale al 1930, W. Empson riconosceva che l'operare dell'a. è alla radice [...] solo a. tra reale e sogno, ma anche tra sogno e sogno nel sogno. Ma non mancano neppure film dallo statuto indecidibile, tipici del cinema moderno, di cui si potrebbero citare i precedenti surrealisti, ma nei quali si avverte anche un ritorno proprio ...
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.