2009-09-26 9 views
6

Sto imparando lambda calcolo, ma non posso sembrano capire la codifica del numero 0.Numeri di chiesa: come codificare lo zero nel calcolo lambda?

come è "funzione che prende in una funzione e un secondo valore e applica la funzione zero volte sull'argomento" un zero? C'è un altro modo per codificare zero? Qualcuno potrebbe aiutarmi a codificare 0?

risposta

12

"funzione che prende in una funzione ed un secondo valore e si applica la funzione zero volte sull'argomento" A è, naturalmente, non è zero. È una codifica di zero. Quando si ha a che fare con il semplice calcolo lambda, è necessario codificare i numeri (così come altri tipi primitivi) in qualche modo, e ci sono alcuni requisiti dettati per ciascuno di questi tipi. Ad esempio, un requisito per i numeri naturali è quello di poter aggiungere 1 a un dato numero, e un altro è quello di essere in grado di distinguere zero da numeri più grandi (se vuoi saperne di più, cerca "Peano Aritmetica"). La popolare codifica che Dario ha citato ti dà queste due cose, e rappresenta anche un intero N da una funzione che fa qualcosa (codificata come argomento f) N volte - che è una sorta di modo naturale di usare i naturali.

Esistono altre codifiche possibili, ad esempio, una volta che è possibile rappresentare elenchi, è possibile rappresentare N come un elenco di N elementi. Queste codifiche hanno i loro pro e contro, ma quello sopra è di gran lunga il più popolare.

+1

Questa è una domanda correlata che ho chiesto in gruppi di google: Dire che ho una funzione f. Come faccio a dimostrare che questo si traduce in un numero naturale 0? Quali altre funzioni ho bisogno per dedurre che la mia funzione f si comporta come uno 0? – unj2

+0

Se si vuole provare che una funzione 'f' è zero sotto la solita codifica, è necessario mostrare che per tutti' g' (f g x) == x. Non hai bisogno di sapere niente al di là di questo. –

13

Vedi wikipedia:

0 ≡ λf.λx. x 
1 ≡ λf.λx. f x 
2 ≡ λf.λx. f (f x) 
3 ≡ λf.λx. f (f (f x)) 
... 
n ≡ λf.λx. fn x 
+0

Perché i downvotes? – Dario

+0

Sono d'accordo - ho rilanciato la tua risposta. Risponde alla domanda! –

+3

Non risponde alla domanda, semplicemente ripete la codifica che l'OP già conosce chiaramente. Semplicemente non capisce COME o PERCHÉ 0 ≡ λf.λx. x (e nemmeno io, che è il motivo per cui sono qui lol) – Ryan

5

Se si impara lambda calcolo, probabilmente già sapete che λxy.y arg1 * * arg2 ridurrà al arg2, dal momento che la x è sostituito dal nulla, e il resto (λy.y) è l'identità funzione.

È possibile scrivere zero in molti altri modi (ad esempio, creare una convenzione diversa), ma ci sono buoni motivi per utilizzare λxy.y. Ad esempio, vuoi che zero sia il primo numero naturale, in modo che se applichi la funzione successore ad esso, ottieni 1, 2, 3 ecc. Con la funzione λabc.b (abc), ottieni λxy.x (y), λxy.x (x (y)), λxy.x (x (x (y))) ecc., in altre parole, si ottiene un sistema di numeri interi.

Inoltre, si desidera che lo zero sia l'elemento neutro rispetto all'addizione. Con la nostra funzione successore S: = λabc.b (abc), possiamo definire n + * m * come n S m, cioè n volte l'applicazione della funzione successore m. Il nostro zero λxy.y soddisfa questo, sia 0 S m e m S 0 ridurre a m.