Pages: [1] 2   Go Down
Print
Author Topic: Re:esercizio esempio beta-Riduzione  (Read 848 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11


« on: 29-12-2017, 12:32:35 »

salve ragazzi, nel libro c'è un esempio che non riesco a capire, qualcuno mi potrebbe descrivere il motivo di quei passaggi?

(\x.y)((\z.zz)(\w.w))  ->b y
« Last Edit: 09-01-2018, 20:09:34 by Franco Barbanera » Logged
Gerasia
Matricola
*
Offline Offline

Posts: 29


« Reply #1 on: 29-12-2017, 18:22:46 »

premetto che neanche io ho chiarissimo come si procede con la b-riduzione, però dovrebbe essere così

(\x.y)((\z.zz)w) ->
(\x.y)ww ->
y

« Last Edit: 01-01-2018, 19:57:51 by Gerasia » Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #2 on: 29-12-2017, 20:47:51 »

premetto che neanche io ho chiarissimo come si procede con la b-riduzione, però dovrebbe essere così

(\x.y)((\z.zz)w) ->
(\x.y)zz ->
y


Da quello che ho capito il procedimento dovrebbe essere questo(spiegato in maniera molto elementare)...

(\x.y)((\z.zz)(\w.w))

partiamo dai due termini dentro la parentesi interna cioè (\z.zz)(\w.w). Ora analizziamo il termine più a sinistra(\z.zz) e ci chiediamo "quante volte la variabile accanto al \ è presente dopo il "." ? " . In questo caso la z è presente 2 volte dopo il punto quindi prendiamo il lambda termine a destra di quello che abbiamo analizzato e lo riscriviamo due volte. avremo quindi a questo punto...

(\x.y)((\w.w)(\w.w)) ripetiamo il procedimento quindi ci chiediamo "quante volte w è presente(nel termine in grassetto) dopo il . ? " 1 volta, quindi riscriviamo il lamda-termine a destra una sola volta...

(\x.y)(\w.w) ripetiamo per l'ultima volta il procedimento. Prendiamo in considerazione (\x.y), x non è presente nemmeno una volta dopo il "." quindi il lamba-termine a destra non viene riscritto. Resta però una y  (\x.y) che sara la soluzione del nostro esercizio.


spero di essere stato abbastanza chiaro [Emoticon] Asd

 
Logged
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11


« Reply #3 on: 29-12-2017, 22:39:40 »

premetto che neanche io ho chiarissimo come si procede con la b-riduzione, però dovrebbe essere così

(\x.y)((\z.zz)w) ->
(\x.y)zz ->
y


Da quello che ho capito il procedimento dovrebbe essere questo(spiegato in maniera molto elementare)...

(\x.y)((\z.zz)(\w.w))

partiamo dai due termini dentro la parentesi interna cioè (\z.zz)(\w.w). Ora analizziamo il termine più a sinistra(\z.zz) e ci chiediamo "quante volte la variabile accanto al \ è presente dopo il "." ? " . In questo caso la z è presente 2 volte dopo il punto quindi prendiamo il lambda termine a destra di quello che abbiamo analizzato e lo riscriviamo due volte. avremo quindi a questo punto...

(\x.y)((\w.w)(\w.w)) ripetiamo il procedimento quindi ci chiediamo "quante volte w è presente(nel termine in grassetto) dopo il . ? " 1 volta, quindi riscriviamo il lamda-termine a destra una sola volta...

(\x.y)(\w.w) ripetiamo per l'ultima volta il procedimento. Prendiamo in considerazione (\x.y), x non è presente nemmeno una volta dopo il "." quindi il lamba-termine a destra non viene riscritto. Resta però una y  (\x.y) che sara la soluzione del nostro esercizio.


spero di essere stato abbastanza chiaro [Emoticon] Asd

  

ah bhè se questo è il ragionamento, ci sono boh, grazie mille per la spiegazione!
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #4 on: 30-12-2017, 18:54:44 »

Di nulla ok
Logged
teo998
Matricola
*
Offline Offline

Posts: 42



WWW
« Reply #5 on: 31-12-2017, 15:16:20 »

Puoi anche considerare che per qualunque sia T:
(\x.y) T -> y

Nel caso del termine (\x.y)((\z.zz)(\w.w)), T è ((\z.zz)(\w.w))
Logged

Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #6 on: 02-01-2018, 12:39:20 »

partiamo dai due termini dentro la parentesi interna cioè (\z.zz)(\w.w). Ora analizziamo il termine più a sinistra(\z.zz) e ci chiediamo "quante volte la variabile accanto al \ è presente dopo il "." ? " . In questo caso la z è presente 2 volte dopo il punto quindi prendiamo il lambda termine a destra di quello che abbiamo analizzato e lo riscriviamo due volte. avremo quindi a questo punto...

Questo ragionamento e' elementare, ma scorretto.

Seguendo questo ragionamento uno potrebbe ridurre
 (\z.\x.(zz))(\w.(xw))
a
\x.((\w.(xw))(\w.(xw)))

Che e' sbagliato!!!

L'unico ragionamento "da seguire"  e':
si prende un sottotermine della forma (\x.M)N e si sotituisce con M[N/x].
Piu' elementare di cosi' si muore.

Ovviamente bisogna aver chiaro come funziona l'operazione di sostituzione [N/x]
Se questa non fosse chiara allora si dovrebbero fare domande specifiche sulle
parti della defionizione di sostituzione che non risultano chiare.



Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #7 on: 04-01-2018, 17:55:15 »


Questo ragionamento e' elementare, ma scorretto.


Ecco perchè provando a fare esercizi un pò più complicati sulla B-riduzione non sono riuscito ad arrivare alla soluzione...chiedo scusa pray
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #8 on: 04-01-2018, 17:59:03 »


L'unico ragionamento "da seguire"  e':
si prende un sottotermine della forma (\x.M)N e si sotituisce con M[N/x].
Piu' elementare di cosi' si muore.


ho provato a fare l'esercizio 53

Dire se il seguente termine possiede forma normale ed eventualmente fornirla insieme ai vari passi di riduzione:
(λxxx.((λxx.x)(xx)(λx.x)))x(xx)

dopo aver sbattuto la testa per un pò di tempo ho guardato la soluzione
 (\xxx.((\xx.x)(xx)(\x.x)))x(xx) --> (\xx.((\xx.x)(xx)(\x.x)))(xx) -->
     --> \x.((\xx.x)(xx)(\x.x)) --> \x.((\x.x)(\x.x)) --> \x.(\x.x)

Non riesco a capire come riusciamo ad arrivare alla soluzione in grassetto applicando la regola che dice lei...
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #9 on: 05-01-2018, 22:16:27 »

professore credo di essere riuscito a capire come risolvere, mi dica se il ragionamento è corretto testate

(λxxx.((λxx.x)(xx)(λx.x)))x(xx)

(\a.(\b.(\x.((\xx.x)(xx)(\x.x)))))x(xx)

((\b.(\x.((\xx.x)(xx)(\x.x))))[x/a])(xx) (resta lo stesso)

(\b.(\x.((\xx.x)(xx)(\x.x))))(xx)

(\x.((\xx.x)(xx)(\x.x)))[(xx)/b] (resta lo stesso)

(\x.((\xx.x)(xx)(\x.x)))

(\x.((\a.(\x.x))(xx)(\x.x)))    \x.x[(xx)/a]  (riduco la parte in grassetto, resta la stessa)

(\x.((\x.x)(\x.x)))         x[(\x.x)/x]

\x.(\x.x)    soluzione

Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #10 on: 06-01-2018, 23:09:23 »

DEVI indicare cosa fai tra un lambda-termine e l'altro!
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #11 on: 06-01-2018, 23:11:05 »

E devi sottolineare i redex che riduci (la notazione standard per indicare il redex che si riduce).
ALtrimenti e' difficile da seguire il procedimento.
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #12 on: 07-01-2018, 21:37:44 »

λxxx.((λxx.x)(xx)(λx.x)))x(xx) (\xxx corrisponde a dire \x.\x.\x...dopo di che affettuo una alfa conversione(abbiamo tre \x!!!)sui primi due per evitare che esistano due o più lamda che leghino variabili con lo stesso nome. Avrò quindi \a.\b.\x

1)(\a.(\b.(\x.((\xx.x)(xx)(\x.x)))))x(xx)

   ((\b.(\x.((\xx.x)(xx)(\x.x))))[x/a])(xx)

2)(\b.(\x.((\xx.x)(xx)(\x.x))))(xx)

   (\x.((\xx.x)(xx)(\x.x)))[(xx)/b]

3)(\x.((\xx.x)(xx)(\x.x)))      (Qui \x.\x lo faccio diventare \a.\x)

   (\x.((\a.(\x.x))(xx)(\x.x)))    \x.x[(xx)/a] 

4) (\x.((\x.x)(\x.x)))         x[(\x.x)/x]

\x.(\x.x)    soluzione



.ora è più comprensibile?
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #13 on: 08-01-2018, 09:47:23 »

.ora è più comprensibile?

poco piu'.

            (\a.(\b.(\x.((\xx.x)(xx)(\x.x)))))x(xx)

-->beta   (\b.(\x.((\xx.x)(xx)(\x.x))))(xx)

-->beta    \x.((\xx.x)(xx)(\x.x))

=alpha   (\x.((\a.\x.x)(xx)(\x.x)))     

-->beta  (\x.((\x.x)(\x.x)))         

-->beta    \x.(\x.x)   

Logged
Gerasia
Matricola
*
Offline Offline

Posts: 29


« Reply #14 on: 08-01-2018, 18:35:53 »

professore, abbiamo provato a fare l'esercizio numero 43 e ora posto la soluzione, mi può dire se è corretto??

           (λxxxx.xx)(λx.xx)(λx.x)y((λx.x)x)

->beta   (λxxxx.xx)(λx.xx)(λx.x)yx
=alpha   (λa.(λb.(λc.(λx.xx))))(λx.xx)(λx.x)yx
->beta   (λb.(λc.(λx.xx)))(λx.x)yx
->beta   (λc.(λx.xx))yx
->beta      λx.xx  (?) testate   boh
->beta   xx
Logged
Pages: [1] 2   Go Up
Print
Jump to: