funzioniricorsive
Mauro Cappelli
Classe delle funzioni computabili o algoritmiche, ossia delle funzioni n-arie f tali che esiste un algoritmo per computare il valore f(x1,...,x{[) per ogni n-pla di [...] 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, controsegno di x, fattoriale di x, somma di x e ...
Leggi Tutto
Matematica
Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo [...] concetto di operazione effettiva (realizzabile cioè mediante a.). Su questa linea si sviluppano il concetto di funzionericorsiva, la definizione delle funzioni mediante l’operatore di astrazione lambda e i sistemi di combinatori di H.B. Curry. Dall ...
Leggi Tutto
Cibernetica
Ernest H. Hutten
di Ernest H. Hutten
Cibernetica
sommario: 1. Introduzione storica. 2. L'epistemologia delle macchine. 3. La struttura informativa delle macchine. 4. Sistema, processo, informazione [...] e generali, di ricorsività o di procedimenti iterativi; alla fine, si è arrivati al concetto molto ampio di funzionericorsiva generale, in cui non appare più l'elemento iterativo (Herbrand-Gödel-Kleene). Il concetto di ricorsività generale precisa ...
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. [...] f 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, definiscono le stesse classi di oggetti computabili. Che esse corrispondano a ciò ...
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
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 [...] T-computabili coincidono con altre due classi di funzioni proposte come totalità delle funzioni calcolabili, cioè con le funzioni definibili con il cosiddetto "λ-calcolo" di A. Church e con le funzioni generali ricorsive di K. Gödel. In ogni caso le ...
Leggi Tutto
ricorsione
Mauro Cappelli
Metodo per definire funzioni in modo tale che la funzione includa sé stessa nella propria definizione. Si tratta di una tecnica di programmazione molto potente e molto sfruttata [...] quando nella definizione compare la chiamata ad altra procedura o funzione che direttamente o indirettamente richiama la procedura o funzione di partenza. La chiamata ricorsiva termina al verificarsi di una condizione particolare, detta di uscita ...
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.