ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto [...] iniziali mediante un numero finito di applicazioni delle regole di sostituzione e di induzione. Esempi di funzioniricorsive primitive sono le comuni funzioni aritmetiche elementari: predecessore di x: pr(1) = 0, pr(x′) = x; segno di x: sg(0) = 0 ...
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 [...] tale che f(x) è il minimo intero m per il quale g(x,m)=0. È un risultato classico che le funzioniricorsive e le macchine di Turing, come pure molti altri formalismi, definiscano le stesse classi di oggetti computabili. Secondo la cosiddetta tesi di ...
Leggi Tutto
ricorsivo
agg. [der. di ricorrere]. – In matematica e in logica matematica, sinon. di ricorrente (nel sign. 3 c); in partic., nella teoria della ricorsività, funzioni r. primitive, quelle che si possono ottenere dalle funzioni iniziali mediante...
definibilita
definibilità s. f. [der. di definibile]. – Possibilità di essere definito. In matematica e in logica matematica, la proprietà che ha un ente di essere calcolabile, per es. mediante funzioni ricorsive.