problema dell’arresto
Fabrizio Luccio
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problema dell’arresto nacque nel 1936, sulla base di studi sugli [...] insiemi infiniti della fine del XIX sec. La sua enunciazione è dovuta ad Alan Turing ed è basata sulla formalizzazione dei modelli primitivi di calcolo sviluppati all’inizio di quel secolo, tra cui la ...
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
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
INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] di E. L. Post, conseguenza diretta dell'indecidibilità del problema dell'arresto della macchina di Turing. Questo problema indecidibile si enuncia dicendo che non esiste alcun procedimento effettivo il quale, date due sequenze di stringhe x1, ..., xn ...
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.