Pages: 1 [2] 3 4   Go Down
Print
Author Topic: Aiuto esercizio Lambda-calcolo  (Read 10111 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Joe
Apprendista Forumista
**
Offline Offline

Posts: 492


« Reply #15 on: 26-03-2013, 13:55:31 »

Non ho capito come si trova la forma normale di una espressione...ad esempio su questa:

(λx.((λy.z)x))((λx.xx)(λx.xx))

 

Professore può spiegarmi come fare?  pray
« Last Edit: 26-03-2013, 13:57:24 by Joe » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.072



WWW
« Reply #16 on: 26-03-2013, 13:59:51 »

Non ho capito come si trova la forma normale di una espressione...ad esempio su questa:

(λx.((λy.z)x))((λx.xx)(λx.xx))

 

Professore può spiegarmi come fare?  pray

Come prima cosa, identifica i possibili redex presenti nel termine,
cioe' i sottotermine della forma (\x.M)N.

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

Posts: 3.072



WWW
« Reply #17 on: 26-03-2013, 14:01:08 »

Scusi prof. è corretta questa sostituzione?:

x(\lambda yx.x)[(yz)/x] \rightarrow x(\lambda ya.a)[(yz)/x] \rightarrow (yz)(\lambda ya.a)

si, pero' le frecce non hanno senso

fb

Grazie mille, ho messo le frecce solo per denotare i passaggi

Immagino, pero' per noi le frecce hanno un altro senso.

FB
« Last Edit: 26-03-2013, 14:29:32 by Franco Barbanera » Logged
Acicatena86
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 404


See full me now who neon


« Reply #18 on: 26-03-2013, 16:15:10 »

Esercizio 31
Professore mi potrebbe dire come procedere?, arrivati al punto  c) mi blocco  cry

Trovare la forma normale (se esiste) di :

(\lambda x.xxy)(\lambda xy.xyy)

a)Metto qualche parentesi e il termine diventa:
((\lambda x.(xx))y))(\lambda x.(\lambda y.(xy)y)) e' corretto?

b) Ricerco le variabili legate, così da poterle rinominare, in particolare io ho fatto le seguenti \alpha-conversioni
((\lambda a.(xx)y))(\lambda x.(\lambda b.(xy)y))  è corretto?

c) Adesso se i punti a-b sono giusti come procedo?

Professore forse ci sono ..  

Allora io ho

(\lambda x.xxy)(\lambda xy.xyy)

a)Metto qualche parentesi e il termine diventa:

((\lambda x.(xx))y))(\lambda x.(\lambda y.(xy)y))

b) Rinomino

\underline{((\lambda a.(aa)y))(\lambda b.(\lambda c.(bc)c))} Ho solo un unico redex ed è quello sottolineato

Il risultato della prima riduzione è il seguente :
\underline{(\lambda b.(\lambda c.(bc)c))(\lambda b.(\lambda c.(bc)c))}y

Anche qui abbiamo un unico redex ed è quello sottolineato

Seconda riduzione :
(\lambda b.(\lambda c.(bc)c))y

Qui ci sono due redex :
  • Questo (\lambda b.\underline{(\lambda c.(bc)c)})y
  • E questo \underline{(\lambda b.(\lambda c.(bc)c))y}

Scelgo il secondo, quindi altra riduzione (y(\lambda c.(yc)c))

In questo caso il redex è uno solo (\lambda c.(yc)c), quindi ultima riduzione e ottengo yyc

Prof. è corretto?
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.072



WWW
« Reply #19 on: 26-03-2013, 16:53:11 »

Non riesco a seguire il ragionamento per come e' scritto.
(forse e' meglio che lo facciamo domani a lezione).

Che il risultato sia sbagliato si vede subito dal fatto che a te risulta
yyc

Ora, 'c'  e' una variabile legata.
Come fa a diventare libera alla fine delle riduzioni?
Se tu vedi come e' fatto un redex e cosa si ottiene dalla sua riduzione
ti accorgerai che e' impossibile che in una riduzione una variabile legata diventi libera.

FB
Logged
rabbit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 136



« Reply #20 on: 26-03-2013, 17:21:38 »

Acicatena86 nel primo esercizio del n°13 hai ridenominato una variabile libera, secondo me la sostituzione non è corretta. Mi sbaglio?
Logged
Joe
Apprendista Forumista
**
Offline Offline

Posts: 492


« Reply #21 on: 28-03-2013, 10:42:29 »

Salve a tutti, ho bisogno di un aiuto riguardo la riduzione in forma normale di una lambda espressione. Innanzitutto vi chiedo se sono corrette le seguenti riduzioni:

1) (\lambda x.yy)(\lambda z.z) x))
      
  • (\lambda x.yy)x
  • yy

2) (\lambda x.((\lambda y.z)x))(\lambda x.xx)(\lambda x.xx))
    
  • (\lambda a.((\lambda y.z)a))\Omega
  • (\lambda a.z)\Omega
  • z

L'aiuto che vi chiedo è, ad esempio, su questa (spiegandomi i passaggi):  testate testate testate

(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)

EDIT: avrei bisogno di aiuto anche su questa:  testate testate testate

(\lambda x.xxy)(\lambda xy.xyy)
« Last Edit: 28-03-2013, 11:30:32 by Joe » Logged
Acicatena86
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 404


See full me now who neon


« Reply #22 on: 28-03-2013, 10:51:31 »

Acicatena86 nel primo esercizio del n°13 hai ridenominato una variabile libera, secondo me la sostituzione non è corretta. Mi sbaglio?

Errore di battitura Smiley .. il lambda termine esatto è
(\lambda y.xy) [yz/x]

(\lambda a.xa)
(\lambda a.yza)

Adesso dovrebbe essere corretto!
« Last Edit: 28-03-2013, 11:11:58 by Acicatena86 » Logged
Acicatena86
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 404


See full me now who neon


« Reply #23 on: 28-03-2013, 11:41:02 »

Salve a tutti, ho bisogno di un aiuto riguardo la riduzione in forma normale di una lambda espressione. Innanzitutto vi chiedo se sono corrette le seguenti riduzioni:

1) (\lambda x.yy)(\lambda z.z) x))
       
  • (\lambda x.yy)x
  • yy

2) (\lambda x.((\lambda y.z)x))(\lambda x.xx)(\lambda x.xx))
   
  • (\lambda a.((\lambda y.z)a))\Omega
  • (\lambda a.z)\Omega
  • z

L'aiuto che vi chiedo è, ad esempio, su questa (spiegandomi i passaggi):  testate testate testate

(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)

1 OK
2 OK

Se non sbaglio  è l'esercizio che abbiamo fatto in aula ieri..  Ricopio dai miei appunti...

(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)

Riscriviamo il lambda termine nel seguente modo

 \left{[(\lambda a.\begin{matrix} \underbrace{( \lambda b.\lambda c.\lambda x. xx)}_{M} \end{matrix}\begin{matrix}\underbrace{(\lambda x.xx)}_{N}\end{matrix}]y \right} x

Quindi..

\left{[(\lambda b.\begin{matrix} \underbrace{(\lambda c.\lambda x.xx)}_{M} \end{matrix}\begin{matrix}\underbrace{(\lambda x.x)}_{N}\end{matrix}]y\right}x


Riduciamo ancora..

\left[(\lambda c.\lambda x.xx)y\right]x

E ancora...

(\lambda x.xx)x

Infine otteniamo  xx
Logged
Joe
Apprendista Forumista
**
Offline Offline

Posts: 492


« Reply #24 on: 28-03-2013, 11:56:03 »

Salve a tutti, ho bisogno di un aiuto riguardo la riduzione in forma normale di una lambda espressione. Innanzitutto vi chiedo se sono corrette le seguenti riduzioni:

1) (\lambda x.yy)(\lambda z.z) x))
       
  • (\lambda x.yy)x
  • yy

2) (\lambda x.((\lambda y.z)x))(\lambda x.xx)(\lambda x.xx))
   
  • (\lambda a.((\lambda y.z)a))\Omega
  • (\lambda a.z)\Omega
  • z

L'aiuto che vi chiedo è, ad esempio, su questa (spiegandomi i passaggi):  testate testate testate

(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)

1 OK
2 OK

Se non sbaglio  è l'esercizio che abbiamo fatto in aula ieri..  Ricopio dai miei appunti...

(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)

Riscriviamo il lambda termine nel seguente modo

 \left{[(\lambda a.\begin{matrix} \underbrace{( \lambda b.\lambda c.\lambda x. xx)}_{M} \end{matrix}\begin{matrix}\underbrace{(\lambda x.xx)}_{N}\end{matrix}]y \right} x

Quindi..

\left{[(\lambda b.\begin{matrix} \underbrace{(\lambda c.\lambda x.xx)}_{M} \end{matrix}\begin{matrix}\underbrace{(\lambda x.x)}_{N}\end{matrix}]y\right}x


Riduciamo ancora..

\left[(\lambda c.\lambda x.xx)y\right]x

E ancora...

(\lambda x.xx)x

Infine otteniamo  xx

Grazie mille, l'ho appena rifatto e mi risulta  (qui il prof. aveva spiegato i passaggi). Mi facevano confondere tutte quelle parentesi, ma ho capito che alcune di quelle le aggiungeva il prof. per delimitare le redex).
Ora provo a fare la seconda espressione che avevo chiesto e posto eventualmente la soluzione.
Logged
Joe
Apprendista Forumista
**
Offline Offline

Posts: 492


« Reply #25 on: 28-03-2013, 13:59:13 »

La seconda espressione l'ha svolta il prof. ieri a lezione, ma non capisco come è che a lui risulta yyy. A me risulta così:

(\lambda x.xxy)(\lambda xy.xyy)

     
  • (\lambda a.aay)(\lambda bc.bcc)
  • (\lambda bc.bcc)(\lambda bc.bcc)y
  • (\lambda b.(\lambda c.bcc))(\lambda b.(\lambda c.bcc))y
  • (\lambda c.(\lambda b.(\lambda c.bcc))cc)y
  • (\lambda v.(\lambda b.(\lambda c.bcc))vv)y
  • (\lambda b.(\lambda c.bcc))y
  • (\lambda c.ycc)

     forse il prof. ha aggiunto una y e quindi:
     
     
  • (\lambda c.ycc)y
  • yyy

    voi cosa dite? 
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.072



WWW
« Reply #26 on: 28-03-2013, 16:43:12 »

Il passaggio tra i punti 5 e 6 e' errato.
Ci sono due 'v' e quindi la 'y' che finisce al posto della 'v' deve essere raddoppiata.

FB
Logged
Joe
Apprendista Forumista
**
Offline Offline

Posts: 492


« Reply #27 on: 30-03-2013, 09:45:06 »

Salve a tutti, ho svolto i seguenti due esercizi riguardanti la \beta-riduzione e vi chiedo se sono corretti:

1) ((\lambda w.(xw))(\lambda y.(yx)))[\lambda x.(w(xy))/x]
         
  • ((\lambda a.(xa))(\lambda b.(bx)))[\lambda x.(w(xy))/x]
  • (\lambda a.((\lambda x.(w(xy)))a))(\lambda b.(b (\lambda x.(w(xy)))))
  • (\lambda x.(w(xy)))(\lambda b.(b(\lambda x.(w(xy)))))
  • (w((\lambda b.(b(\lambda x.(w(xy)))))y))
  • (w(y(\lambda x.(w(xy)))))

2) (\lambda xy.yx)(\lambda xy.x(yy))(\lambda x.xz(\lambda y.yy))
         
  • (\lambda x.(\lambda y.yx))(\lambda x.(\lambda y.x(yy)))(\lambda x.xz(\lambda y.yy))
  • (\lambda x.(\lambda a.ax))(\lambda x.(\lambda b.x(bb)))(\lambda c.cz(\lambda d.dd))
  • (\lambda a.a(\lambda x.(\lambda b.x(bb))))(\lambda c.cz(\lambda d.dd))
  • ((\lambda c.cz(\lambda d.dd))(\lambda x.(\lambda b.x(bb))))
  • (((\lambda x.(\lambda b.x(bb)))z)(\lambda d.dd))
  • ((\lambda b.z(bb))(\lambda d.dd)
  • (z((\lambda d.dd)(\lambda d.dd)))
       
       
« Last Edit: 30-03-2013, 09:48:04 by Joe » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.072



WWW
« Reply #28 on: 31-03-2013, 17:32:45 »

Mi pare di si.

Salutissimi
FB
Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #29 on: 31-03-2013, 17:35:13 »

http://www.itu.dk/people/sestoft/lamreduce/lamframes.html controllate i risultati qua.

P.S.
le espressioni si scrivono così:  (\x.x x) a
« Last Edit: 31-03-2013, 17:36:51 by Pandemia000 » Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
Pages: 1 [2] 3 4   Go Up
Print
Jump to: