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
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
La funzione testimoniale dell’immagine
Pietro Montani
Ground Zero
Nell’archivio delle immagini cui sarà consegnata la memoria del 21° sec., una posizione di assoluto rilievo spetta sicuramente alla [...] già interessato un pubblico planetario), ma anche e soprattutto perché la sua intensità qualitativa restava indecidibile. Oggettivamente intrise di esteticità, quelle immagini si sottraevano a ogni possibile risoluzione nell’apprezzamento estetico ...
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
salute
Stefano Rodotà
La salute come diritto fondamentale dell’individuo
Definita dall’Organizzazione mondiale della sanità come «una condizione di pieno benessere fisico, psichico e sociale, e non [...] giunge al nucleo duro dell’esistenza, alla necessità di rispettare la persona umana in quanto tale, siamo di fronte all’indecidibile. Nessuna volontà esterna, fosse pure quella coralmente espressa da tutti i cittadini o da un Parlamento unanime, può ...
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 [...] è vera, non necessariamente è vera la sua negazione «non A»; tale proposizione potrebbe infatti essere indecidibile. La impossibilità di utilizzare tale principio implicherebbe per la matematica un sacrificio enorme perché tutte le → dimostrazioni ...
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 [...] descritte; taluni, per esempio, possiedono un insieme di simboli primitivi molto astratto, per esempio non numerabile o indecidibile, altri ammettono formule o dimostrazioni anche di lunghezza infinita. Per questi, come per gli altri, vale sempre ...
Leggi Tutto
decidibilita
decidibilità termine utilizzato nella teoria della calcolabilità per indicare l’esistenza di una procedura algoritmica che permetta di stabilire, in un numero finito di passi, se una data [...] del valore di verità che gli si attribuisce. Il teorema di Gödel afferma che l’aritmetica formalizzata come calcolo logico (mediante gli assiomi di Peano) è una teoria indecidibile perché esistono in essa formule vere che non sono dimostrabili. ...
Leggi Tutto
FEDERICO II, ATTIVITÀ POETICA
SStefano Rapisarda
Sono sei i componimenti che, con vario grado di attendibilità, diversi testimoni assegnano al nome di Federico. Pressoché certa è l'attribuzione della [...] e meritanza" e la ricchezza, se antica o recente non viene specificato, di per sé non è nobilitante.
Possibile, seppur sostanzialmente indecidibile (Contini, 1952, pp. 388, 395), è l'attribuzione di Poiké ti piace,Amore, che nel Palatino reca il nome ...
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 [...] , non è 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 ...
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.