ricorsività
Indice
Definizione
sf. [da ricorsivo]. In logica matematica, teoria elaborata da T. Skolem nel 1919 nel tentativo di fare una trattazione dell'aritmetica che consentisse di evitare riferimenti a domini infiniti e quindi evitasse le difficoltà rappresentate dalle antinomie e le complessità della teoria dei tipi. Negli anni Trenta del sec. XX, in connessione con le ricerche sul problema della decisione e nell'ambito dei tentativi di dare una definizione matematicamente rigorosa delle nozioni intuitive di computabilità effettiva e di costruttivo, la teoria della ricorsività venne ulteriormente approfondita e sviluppata da J. Herbrand, K. GödelS. C. Kleene. Questi autori elaborarono la teoria delle funzioni ricorsive primitive che trovò il suo primo impiego nella memoria di Gödel (1931) sulle proposizioni formalmente indecidibili dei Principia Mathematica. Negli anni successivi si ebbero importanti studi sulle nozioni di computabilità e di ricorsività e sui rapporti tra queste nozioni che portarono all'elaborazione della nozione di ricorsività generale a opera di Kleene (1936). Premesso che si prendono in esame funzioni aritmetiche, ossia funzioni i cui argomenti sono numeri naturali (0, 1, 2, 3,...) e i cui valori sono ancora numeri naturali, consideriamo due processi di definizione assai comuni in matematica per definire nuove funzioni e cioè il processo di sostituzione e quello di definizione induttiva. Siano h₁,...,h delle funzioni di n argomenti (r≥1, n≥0) e sia g una funzione di r argomenti. Se per r argomenti arbitrari si ha f(r)=g[h₁(r),...,h(r)], dove r sta per x₁,...,x, allora si dice che f è ottenuta da g per sostituzione di h₁,...,h. Si dice allora che f(r) è uno schema di sostituzione. Si può inoltre, se le funzioni g, h₁,...,h sono date, ritenere la suddetta relazione quale possibile definizione della funzione f. Data la funzione g di n argomenti (n≥0) e data h come funzione di n+2 argomenti, se abbiamo per argomenti arbitrari r e y
dove y´ sta per y+1, possiamo allora dire che f è definita induttivamente dalle due relazioni di cui sopra per mezzo di g e di h. Diciamo allora che tali relazioni sono uno schema di induzione (o di ricursione). Consideriamo ora le tre seguenti funzioni che diciamo fondamentali
(a) è detta funzione di successore; (b) è detta funzione costante (e si può indicare con C); (c) è detta funzione di identità o di selezione (e si può indicare con U). Definiamo ora come funzioni ricorsive primitive quelle funzioni che sono o una delle funzioni fondamentali o sono ottenibili da una di queste con un numero finito di applicazioni dei procedimenti di sostituzione e di induzione. Intuitivamente parlando, le funzioni fondamentali sono computabili. Inoltre f è computabile nel caso dello schema di sostituzione se g e h₁,...,h sono computabili, e così pure f è computabile nel caso dello schema di induzione se g e h sono computabili. Vediamo così che i procedimenti di sostituzione e di definizione induttiva non fanno altro che condurre da funzioni computabili a funzioni ancora computabili. Si può quindi concludere che le funzioni ricorsive primitive sono tutte funzioni computabili e si può inoltre dimostrare che tutte le più importanti funzioni aritmetiche sono funzioni ricorsive primitive. Va rilevato che queste ultime non esauriscono tutta la classe delle funzioni intuitivamente computabili.
Le funzioni ricorsive generali
Si può definire una funzione ricorsiva generale per mezzo di un sistema di equazioni nel modo seguente. Diciamo che sono termini aritmetici ogni costante individuale, ogni variabile individuale e f(x₁,...,x), se f è una funzione a n argomenti e x₁,...,x sono termini aritmetici. Chiamiamo equazione un'espressione della forma x₁=x₂, dove x₁ e x₂ sono termini aritmetici. Consideriamo ora due operazioni: RS e RR. RS consiste nel sostituire simultaneamente e in modo uniforme, in una data equazione, tutte le variabili occorrenti con delle costanti. Per quanto riguarda l'operazione RR, data una prima equazione in cui non occorrano variabili e il cui termine destro sia costituito da un'unica costante, e data una seconda equazione in cui non occorrano variabili e nel cui termine destro occorra il termine sinistro della prima, è possibile passare a una terza equazione (operazione RR) il cui termine sinistro è quello della seconda e il cui termine destro è ottenuto dal termine destro della seconda rimpiazzandovi il termine sinistro della prima con il termine destro della prima. Si dice che una funzione a n argomenti è ricorsiva generale se esiste un sistema di equazioni che la definisce ricorsivamente, cioè se vi è un sistema di equazioni tale che per ogni successione di costanti a₁,...,a si possa derivare, per mezzo di RS e RR, un'equazione della forma f(a₁,...,a)=b, e ciò per una sola costante B. Il sistema definente deve essere quindi tale che per ogni sistema di argomenti possiamo effettivamente ottenere il valore della funzione che deve essere unico. Il sistema di equazioni conterrà ovviamente anche altre funzioni oltre la definenda, e cioè funzioni ausiliarie di cui il sistema consente il calcolo dei valori e che vengono eventualmente impiegate appunto nel calcolo della funzione considerata. La ricorsività generale include la ricorsività primitiva e ogni funzione ricorsiva generale è computabile. In conseguenza di ciò fu possibile a Church formulare la sua tesi secondo la quale ogni funzione effettivamente computabile è ricorsiva generale e viceversa (1936), pervenendo così a un'esatta determinazione matematica della nozione di calcolabilità effettiva.
Il predicato ricorsivo
Una nozione di particolare interesse nella teoria della ricorsività è quella di predicato ricorsivo. Il predicatoPr è ricorsivo (primitivo) se e solo se esiste una funzione ricorsiva (primitiva) f(r) tale che si annulli per tutti e soli gli argomenti r a cui il predicato conviene. Ora, a ogni predicato può essere associata una funzione caratteristica di quel predicato: la n-aria funzione f è la funzione caratteristica dell'n-ario predicato se e solo se per tutti gli r: [Pr↔f(r)=0]∧[¬Pr↔f(r)=1] la funzione non può prendere altri valori. Ogni predicato ha esattamente una funzione caratteristica, per cui si può asserire che un predicato P è ricorsivo (primitivo) se e solo se la funzione caratteristica di P è ricorsiva (primitiva). Sempre facendo ricorso alla nozione di funzione caratteristica è possibile definire quella di classe o quella di insieme ricorsivi. Lo sviluppo della ricorsività non solo portò decisivi contributi alle ricerche su computabilità, definibilità e problema della decisione a opera di Gödel, Kleene, J. B. Rosser, E. Post e A. M. Turing, ma trovò fruttuosa applicazione nelle indagini su particolari problemi della matematica tradizionale a opera di Post, Turing, A. A. Markov e altri. Inoltre, le ricerche sull'aritmetica ricorsiva sono sfociate in quelle sull'analisi ricorsiva a opera di R. L. Goodstein.