calcolabile = ricorsivo - Carlo Toffalori Flavio Corradini Stefano Leonesi Stefano Mancini. Teo

Per la precisione afferma:

Tesi di Church (1936). Una funzione parziale

f

da l a N ammette un algoritmo di calcolo se e solo se

f è

parziale ricorsiva. In particolare, per

f

totale,

f

ammette un algoritmo di calcolo se e solo se

f è

ricorsiva. Finalmente, un sottoinsieme

L

Nk

ammette un algoritmo di decisione se e solo se

L è

ricorsivo.

Come già la Tesi a proposito delle macchine di Turing, anche questa Tesi di Chur-ch non si propone come un teorema da dimostrare, ma piuttosto come la affer-mazione (che si può condividere o rifiutare) che le nozioni di funzione e insieme ricorsivi costituiscono il modo rigoroso e preciso di introdurre il concetto intuiti-vo di algoritmo. Naturalmente, c'è da chiedersi quanto credito possiamo dare a questa ipotesi. Non ci sono dubbi ad accettare che tutto quanto è ricorsivo am-mette un algoritmo di calcolo o di decisione: la definizione stessa di ricorsività si preoccupa di garantire questa situazione. Semmai c'è da chiedersi se è vero an-che il contrario, se cioè tutte le funzioni an-che hanno un algoritmo di calcolo e tutti gli insiemi che hanno un algoritmo di decisione corrispondono alla condizione di ricorsività. Il prossimo paragrafo è dedicato a fornire qualche semplice esempio al riguardo.

Per completare questo paragrafo, osserviamo nuovamente come l'approccio alla calcolabilità tramite la ricorsività, anche se definito nel caso specifico dei numeri naturali, si estende facilmente a funzioni e linguaggi su ogni alfabeto finito, grazie alle usuali procedure di codifica.

4.3 Esempi a volontà

In realtà neppure oggi sono noti casi di funzioni che ammettano un algoritmo di calcolo e non si dimostrino contemporaneamente (parziali) ricorsive. Lo stesso vale per gli insiemi. Del resto, se e quando si mostrerà che la Tesi di Church non è adeguata al progresso dei calcolatori e delle procedure di calcolo, non sarà il caso di farne un dramma: si prenderà atto che il modello della ricorsività è superato e si provvederà a cercarne un altro più aggiornato.

Vediamo comunque adesso alcuni semplici esempi di funzioni e insiemi che han-no manifestamente un algoritmo di calcolo o di decisione e che si dimostrahan-no ricorsivi.

Esempi.

1. Mostriamo che le quattro operazioni elementari dei numeri naturali (addizio-ne, moltiplicazio(addizio-ne, sottrazione e divisione) corrispondono alla definizione di funzione ricorsiva. Cominciamo con la addizione. La funzione totale binaria + che associa ad ogni coppia ordinata (x, y) di naturali la loro somma x + y è ricorsiva, infatti + si può ottenere per recursione e composizione da funzioni iniziali nel modo che segue: per ogni scelta di x, y E N,

x + O = P1 (x),

x + (y + 1) = s(x y) = s(n(x, y, x y)).

2. Anche la moltiplicazione - è ricorsiva perchè si ottiene per recursione e com-posizione dalle funzioni iniziali e dalla addizione, che già sappiamo essere ricorsiva: infatti, per ogni scelta di x, y E NT,

x • O = O = Z(x),

x • (y +1) = x•y + x = 131(x, y, x • y) + y, x • y).

3. Anche la funzione 2-aria di esponenziazione exp, quella che ad ogni coppia ordinata di naturali (x, y) associa xY è ricorsiva. In realtà si può discutere se exp sia totale oppure parziale, visto che in genere iP non ha significato.

Possiamo comunque convenire in questo caso exp(0, O) = 1. Allora non è difficile controllare in dettaglio che exp si ottiene per recursione e minimaliz-zazione da funzioni iniziali e da • nel modo che segue: per ogni scelta di x, y E N,

exp(x, O) = 1 = s(Z(x)),

exp(x, y + = 131(x, y, exp(x, y)) • Mx, y, exp(x, y)).

4. Il meccanismo della recursione aiuta anche a dimostrare la ricorsività di alcuni semplici esempi di funzioni totali 1-arie, che ci saranno utili nel seguito. Per cominciare, consideriamo la funzione pd (predecessore) che ad ogni naturale y > O associa, appunto, il numero che lo precede, e cioè y — 1; conveniamo

icillhlilllii111;.111111111111111

poi per semplicità

pd(0) =

O. Allora

pd è

ricorsiva, in quando è definita come segue, in accordo col meccanismo di recursione:

pd(0) =

pd(y +

1) =

y = 111(y,

pd(y)) Vy E N.

Allo stesso modo si verifica che la funzione

segno sg,

quella che ad ogni naturale y associa 1 se y O e O se y= O, è ricorsiva: infatti

sg(0) =

sg(y +

1) = 1 =

s(Z (P12 (y, pd(y))))

Vy E N.

Il lettore potrà controllare per esercizio che anche la funzione che viene chia-mata

controsegno

ed indicata 79, quella che ad ogni naturale y associa O se y O e l se y= O, è ricorsiva.

5. Passiamo adesso alla funzione — di sottrazione. Essa è manifestamente non totale tra i naturali: ad esempio, non possiamo calcolare in N 2 — 3, o in generale

x

— y quando

x <

y. Per rimediare, possiamo procedere come negli esempi di

exp

pd

e cercare di convenire valori fittizi per la differenza di

x

e y quando

x <

y. Si considera allora, ad esempio, la funzione

e,

^chiamata

differenza aritmetica

e definita come segue: per ogni scelta di

x

e y naturali, xeyèx—y se

x

— y si può fare, cioè se

x

> y, O altrimenti. La funzione così introdotta è ricorsiva. Per dimostrarlo, ricorriamo all'aiuto della funzione predecessore

pd

e osserviamo che, per ogni scelta di

x,

y E N,

xeo=x=g(x),

x e

^{(y l) =}

pd(n (x, y, x e

^y))•

Quindi

e

si ottiene per recursione e composizione da funzioni ricorsive (in-clusa

pd)

e di conseguenza è ricorsiva. Un altro possibile surrogato totale della sottrazione è la così detta

differenza assoluta,

la funzione che ad ogni coppia di naturali

x

e y associa il valore assoluto della differenza lx

— yl.

Anche questa funzione è ricorsiva perchè è facilmente controllato che, per ogni scelta di

x

e y

— =

(x

y) (y

ex).

6. Consideriamo finalmente la funzione

sottrazione —,

e non più i suoi surrogati.

Abbiamo già osservato che, per xi, x2 E N, l'esistenza della differenza

x1

—x2 dipende dal fatto che x 1 > x2; d'altra parte, xi > x2 se e solo se esiste un y tale che x2 + y =

x 1 ,

condizione che possiamo anche scrivere, ricorrendo alla differenza assoluta, come (x 2 y) —

xi

= O. In questo caso, x1 — x2 è proprio il minimo (in realtà l'unico) y con questa proprietà. Grazie al meccanismo di minimalizzazione, possiamo allora concludere che anche — è parziale ricorsiva.

7. Lo stesso vale per le funzioni q e r che ad ogni coppia di naturali xi e 12 con 1 2 O associano, rispettivamente, il

quoziente e

il

resto

della divisione di xi per 12. Come già sottolineato, queste funzioni sono definite se e solo se x2 O; una maniera un po' involuta di esprimere questa condizione è quella di affermare che qualche multiplo di 12 prima o poi supera xi: infatti, per 12 = O, l'unico numero divisibile per 12 è O stesso, e non può oltrepassare

x1;

ma altrimenti la sequenza strettamente crescente O •

x12,

1 • x2, 2 - x2, ... finisce col diventare maggiore di Quindi possiamo affermare che

e r sono definiti su

(xi, 12) se e solo se esiste y tale che (y+1) > ; quest'ultima condizione si può anche esprimere dicendo che la differenza aritmetica (y + 1) •

n e xi

è maggiore di O, ovvero che il suo controsegno è O

sg((y + -

e

x i ) =

o.

In questo caso, il quoziente di xi per /2 è proprio il minimo y per cui (y + 1) • /2

> xi

(in altre parole, il massimo per cui y • /2 < xi)

q(xi

, 12) =

miri {y E N : -s-g((y +

1) • x 2 e

x i ) =

o},

Nel documento Carlo Toffalori Flavio Corradini Stefano Leonesi Stefano Mancini. Teoria della computabilità e della complessità. McGraw-Hill (pagine 72-75)