Funzioni ricorsive primitive
Buongiorno (o buonasera) a tutti.
Proseguendo con lo studio di Gödel e dei teoremi d'incompletezza mi sono imbattuto nella ricorsione primitiva.
Leggo: una funzione numero-teoretica \(\displaystyle \phi (x_1, x_2, ..., x_n) \) è detta ricorsivamente definita nei termini delle funzioni numero-teoretiche \(\displaystyle \psi (x_1, x_2, ..., x_n-1)\) [il \(\displaystyle -1 \) dovrebbe essere sotto, accanto alla n, ma non riesco a scriverlo] e \(\displaystyle \mu(x_1, x_2, ..., x_n+1)\) [idem come sopra] SE sono valide le equazioni:
\(\displaystyle \phi(0, x_2, ..., x_n) = \psi(x_2, ..., x_n) \) ,
\(\displaystyle \phi(k+1, x_2, ..., x_n) = \mu(k, \phi(k, x_2, ..., x_n), x_2, ..., x_n) \)
per tutti gli \(\displaystyle x_2, ..., x_n, k \).
Ma prendiamo l'esempio della funzione Addizione (+), che dovrebbe essere una delle più semplici. Essa può essere definita mediante ricorsione primitiva a partire dalla funzione base Successore (S).
La funzione Successore è questa:
\(\displaystyle S(x) = x + 1 \)
Per definire ricorsivamente l'addizione, allora, trovo scritto:
\(\displaystyle + (x, 0) = x \)
\(\displaystyle + (x, S(y)) = S(+ (x,y)) \)
E qui non capisco.
Cosa vuol dire che la funzione addizione viene definita "a partire da" un'altra funzione? Vedo che la funzione Successore compare due volte nella seconda formula, ma non riesco a capire il motivo, o almeno il modo.
Qualcuno potrebbe essere così gentile da spiegarmi passo per passo (anche con osservazioni che riterreste banali) il procedimento da seguire? Ho preso in esempio una funzione (addizione) semplice, ma in realtà Gödel fa esempi più complessi. Vorrei partire dalle basi
Proseguendo con lo studio di Gödel e dei teoremi d'incompletezza mi sono imbattuto nella ricorsione primitiva.
Leggo: una funzione numero-teoretica \(\displaystyle \phi (x_1, x_2, ..., x_n) \) è detta ricorsivamente definita nei termini delle funzioni numero-teoretiche \(\displaystyle \psi (x_1, x_2, ..., x_n-1)\) [il \(\displaystyle -1 \) dovrebbe essere sotto, accanto alla n, ma non riesco a scriverlo] e \(\displaystyle \mu(x_1, x_2, ..., x_n+1)\) [idem come sopra] SE sono valide le equazioni:
\(\displaystyle \phi(0, x_2, ..., x_n) = \psi(x_2, ..., x_n) \) ,
\(\displaystyle \phi(k+1, x_2, ..., x_n) = \mu(k, \phi(k, x_2, ..., x_n), x_2, ..., x_n) \)
per tutti gli \(\displaystyle x_2, ..., x_n, k \).
Ma prendiamo l'esempio della funzione Addizione (+), che dovrebbe essere una delle più semplici. Essa può essere definita mediante ricorsione primitiva a partire dalla funzione base Successore (S).
La funzione Successore è questa:
\(\displaystyle S(x) = x + 1 \)
Per definire ricorsivamente l'addizione, allora, trovo scritto:
\(\displaystyle + (x, 0) = x \)
\(\displaystyle + (x, S(y)) = S(+ (x,y)) \)
E qui non capisco.
Cosa vuol dire che la funzione addizione viene definita "a partire da" un'altra funzione? Vedo che la funzione Successore compare due volte nella seconda formula, ma non riesco a capire il motivo, o almeno il modo.
Qualcuno potrebbe essere così gentile da spiegarmi passo per passo (anche con osservazioni che riterreste banali) il procedimento da seguire? Ho preso in esempio una funzione (addizione) semplice, ma in realtà Gödel fa esempi più complessi. Vorrei partire dalle basi
Risposte
Non so se ho capito con esattezza cosa non ti è chiaro:
per definire una funzione tramite ricorsione primitiva devi definire il valore di quella funzione per $y = 0$ e per $y = k+1$ potendo utilizzare il valore della stessa funzione per $y = k$. Nel "sistema" ovviamente $k+1$ è rappresentato da $ S(bar (k) ) $.
Di conseguenza puoi definire informalmente l'addizione in questo modo:
$x + 0 = x$
$x + (y+1) =(x+y) + 1$
Ovviamente per sommare uno devi utilizzare la funzione successore, non la somma, e quindi, formalmente, otteniamo:
$+(x,0) = x$
$+(x,S(y)) =S(+(x,y))$
per definire una funzione tramite ricorsione primitiva devi definire il valore di quella funzione per $y = 0$ e per $y = k+1$ potendo utilizzare il valore della stessa funzione per $y = k$. Nel "sistema" ovviamente $k+1$ è rappresentato da $ S(bar (k) ) $.
Di conseguenza puoi definire informalmente l'addizione in questo modo:
$x + 0 = x$
$x + (y+1) =(x+y) + 1$
Ovviamente per sommare uno devi utilizzare la funzione successore, non la somma, e quindi, formalmente, otteniamo:
$+(x,0) = x$
$+(x,S(y)) =S(+(x,y))$
"Deckard":
Non so se ho capito con esattezza cosa non ti è chiaro:
per definire una funzione tramite ricorsione primitiva devi definire il valore di quella funzione per $y = 0$ e per $y = k+1$ potendo utilizzare il valore della stessa funzione per $y = k$. Nel "sistema" ovviamente $k+1$ è rappresentato da $ S(bar (k) ) $.
Di conseguenza puoi definire informalmente l'addizione in questo modo:
$x + 0 = x$
$x + (y+1) =(x+y) + 1$
Ovviamente per sommare uno devi utilizzare la funzione successore, non la somma, e quindi, formalmente, otteniamo:
$+(x,0) = x$
$+(x,S(y)) =S(+(x,y))$
Allora, cerco di ripercorrere passo dopo passo il procedimento.
• Prendo una funzione come +(x,y) da definire ricorsivamente
1) Definisco il valore di quella funzione per $y = 0$, quindi:
$+(x,0) = x$
Prima domanda: perché Gödel scrive invece \(\displaystyle \phi(0, x_2, ..., x_n) \), mettendo prima lo $0$, prendendolo come se fosse $x_1$? E' indifferente la sua posizione?
2) Definisco il valore di quella funzione per $y = k+1$, (con $y = k$) quindi:
$+(x,S(y)) = ...$
Ma a questo punto, al posto dei puntini di sospensione, qualcosa non mi quadra. Lo "schema" della ricorsione dice che in quel punto va \(\displaystyle \mu(k, \phi(k, x_2, ..., x_n), x_2, ..., x_n) \)
quindi dovrebbe essere qualcosa come \(\displaystyle \mu(y, +(y,x), x) \), o sbaglio? Mi blocco a questo punto. Al posto di $\mu$ cosa andrebbe? Immagino che sia qualcosa di piuttosto semplice da capire, ma probabilmente seguo una strada sbagliata in partenza.
Preciso che intuitivamente il "significato" della formula così come l'hai scritta mi è chiaro. Ma quando lo collego allo schema della ricorsività non capisco come sia stato ottenuto, come vadano effettuate le sostituzioni, mi perdo.
La funzione successore è la nostra $mu$.
"Deckard":
La funzione successore è la nostra $mu$.
1) Ma come facciamo a sapere che sarà proprio Successore, e non (ad esempio) una funzione di proiezione? A livello intuitivo lo capisco, ma a livello "meccanico" come ci arriviamo?
2) Inoltre, anche dopo aver usato il successore al posto di $\mu$, sbaglio o otteniamo: \(\displaystyle S(y, +(y,x), x) \) ?
E a questo punto come arriviamo a \(\displaystyle S(+(y,x)) \) ?
No, era la strada sbagliata.
Ho trovato sulla Stanford Encyclopedia of Philosophy quella che mi sembra la soluzione:
la formula \(\displaystyle S(+(y,x)) \) è ottenuta tramite la composizione della funzione successore e della funzione proiezione su \(\displaystyle \mu(y, +(y,x), x) \). Cioè:
\(\displaystyle S(+(y,x)) = [s\circ p_2] (y, +(y,x), x) \)
Insomma, $\mu$ non è la funzione successore, ma la composizione della funzione successore e della funzione di composizione.
Mi manca ancora qualcosa per comprendere a pieno il procedimento, ma questo passaggio mi serviva.
Ho trovato sulla Stanford Encyclopedia of Philosophy quella che mi sembra la soluzione:
la formula \(\displaystyle S(+(y,x)) \) è ottenuta tramite la composizione della funzione successore e della funzione proiezione su \(\displaystyle \mu(y, +(y,x), x) \). Cioè:
\(\displaystyle S(+(y,x)) = [s\circ p_2] (y, +(y,x), x) \)
Insomma, $\mu$ non è la funzione successore, ma la composizione della funzione successore e della funzione di composizione.
Mi manca ancora qualcosa per comprendere a pieno il procedimento, ma questo passaggio mi serviva.
Buongiorno, torno ad aggiornare il thread chiedendo un aiuto.
Ho $\gamma (x,y) = 0$ se $x = y$, e $\gamma (x,y) = 1$ se $x \ne y$.
In pratica si tratta della relazione di uguaglianza (solo che i valori di verità in questa formalizzazione sono invertiti: 1 per la falsità e 0 per la verità).
Vorrei dimostrare che $\gamma (x,y)$ è una funzione ricorsiva. Potreste darmi una mano su come procedere? Cosa devo mettere a sistema? Suppongo che la prima parte sia qualcosa come:
$\gamma (x,0) = ?$
P.S. Non riesco a mettere in sistema queste formule...appena c'è la virgola tra (x,0) il codice non va.
Ho $\gamma (x,y) = 0$ se $x = y$, e $\gamma (x,y) = 1$ se $x \ne y$.
In pratica si tratta della relazione di uguaglianza (solo che i valori di verità in questa formalizzazione sono invertiti: 1 per la falsità e 0 per la verità).
Vorrei dimostrare che $\gamma (x,y)$ è una funzione ricorsiva. Potreste darmi una mano su come procedere? Cosa devo mettere a sistema? Suppongo che la prima parte sia qualcosa come:
$\gamma (x,0) = ?$
P.S. Non riesco a mettere in sistema queste formule...appena c'è la virgola tra (x,0) il codice non va.
Scusatemi se aggiorno la discussione, sono ancora bloccato su questo passaggio.
Qualcuno sarebbe così gentile da darmi una mano?
Qualcuno sarebbe così gentile da darmi una mano?
Buongiorno a tutti, torno ad aggiornare il thread per porre un'altra domanda, spero piuttosto semplice per chi conosce la matematica meglio di me.
Una relazione $ R (x_1, ... , x_n) $ tra numeri naturali si dice ricorsiva primitiva se esiste una funzione ricorsiva primitiva $ \phi (x_1, ... , x_2) $ tale che, per tutti gli $ x_1 , x_2 , ... , x_n $,
\[R(x_1, ... , x_n) \leftrightarrow \phi (x_1, ... , x_2)=0\]
Potreste gentilmente spiegarmi a cosa serve quel $ = 0 $ alla fine? Vuol dire che La relazione $ R (x_1, ... , x_n) $ è ricorsiva solo se la funzione $ \phi $ restituisce solo valore 0? E se è così, perché?
Una relazione $ R (x_1, ... , x_n) $ tra numeri naturali si dice ricorsiva primitiva se esiste una funzione ricorsiva primitiva $ \phi (x_1, ... , x_2) $ tale che, per tutti gli $ x_1 , x_2 , ... , x_n $,
\[R(x_1, ... , x_n) \leftrightarrow \phi (x_1, ... , x_2)=0\]
Potreste gentilmente spiegarmi a cosa serve quel $ = 0 $ alla fine? Vuol dire che La relazione $ R (x_1, ... , x_n) $ è ricorsiva solo se la funzione $ \phi $ restituisce solo valore 0? E se è così, perché?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo