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 [...] in grado di decidere per il sì o per il no; e ancora è provata l'esistenza di linguaggi ricorsivamenteenumerabili non ricorsivi. Quest'ultima asserzione costituisce una forma astratta del teorema di Gödel che stabilisce che ogni sistema assiomatico ...
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. [...] sui gruppi context-free.
Il quarto e ultimo livello della gerarchia è costituito dalla classe dei linguaggi ricorsivamenteenumerabili. Essa viene introdotta mediante le macchine di Turing. Definiremo anche la corrispondente classe di funzioni ...
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 [...] finale, ma è importante osservare che può anche non fermarsi mai. Un linguaggio L riconosciuto da una macchina di Turing si dice ricorsivamenteenumerabile; se è ricorsivamenteenumerabile anche il suo complementare, il linguaggio prende il nome di ...
Leggi Tutto
enumerabileenumeràbile [agg. Der. del lat. numerus "numero"] [ALG] Insieme e.: insieme per cui esiste un procedimento effettivo per stabilire una corrispondenza biunivoca tra i suoi elementi e i numeri [...] naturali. ◆ [ALG] [INF] Insieme ricorsivamente e.: v. automi, teoria degli: I 332 c. ...
Leggi Tutto
esclusione
escluṡióne s. f. [dal lat. exclusio -onis, der. di excludĕre «escludere»]. – 1. L’atto, il fatto di escludere o di essere escluso: e. da un’assemblea, dagli esami; e. dal diritto di voto (in determinati casi contemplati dalla legge);...