Stephen Cole Kleene ha escogitato un modo per eseguire la sottrazione di interi utilizzando l'aggiunta di interi. Tuttavia, presuppone che non è possibile avere numeri interi negativi. Ad esempio:
0 - 1 = 0
1 - 1 = 0
2 - 1 = 1
3 - 1 = 2
4 - 1 = 3
5 - 2 = 3
6 - 3 = 3
6 - 4 = 2
6 - 5 = 1
6 - 6 = 0
6 - 7 = 0
Nella domanda è stata implementata l'operazione di aggiunta utilizzando l'operazione di incremento.
Allo stesso modo, è possibile implementare l'operazione di sottrazione utilizzando l'operazione di decremento nel seguente modo:
sub(x, y) {
loop y
{ x = decr(x) }
return x
}
Ora, tutto quello che dobbiamo fare è implementare l'operazione di decremento.
Questo è dove il genuis di Kleene brilla:
decr(x) {
y = 0
z = 0
loop x {
y = z
z = incr(z)
}
return y
}
Qui abbiamo utilizzato tutte le quattro operazioni. Ecco come funziona:
abbiamo due casi di base, y
(il caso base per 0
) e z
(caso base per 1
):
y = 0 - 1 = 0
z = 1 - 1 = 0
Quindi, abbiamo entrambi inizializziamo a 0
.
Quando x
è 0
corriamo il ciclo 0
volte (cioè mai) e poi abbiamo semplicemente tornare y = 0
.
Quando x
è 1
poi eseguire il ciclo una volta, assegnare y = z
e poi semplicemente ritorno y = z = 0
.
Si noti che ogni volta che esegue il ciclo y
detiene il risultato dell'iterazione corrente mentre z
tiene il risultato della successiva iterazione. Questo è il motivo per cui abbiamo bisogno di due casi base. La funzione di decremento non è una funzione continua. Si tratta di una funzione piecewise:
decr(0) = 0
decr(n + 1) = n
Kleene capito questo quando è andato dal dentista e il dentista estratto due denti. Era frustrato mentre cercava di risolvere questo problema e quando il dentista estrasse due dei suoi denti si rese conto che aveva bisogno di due casi base.
fonte
2015-12-04 00:51:03
Sei sicuro che sia possibile? Sembra che qualsiasi nuovo valore che crei sia una costante fissa o una funzione affine positiva degli input. – templatetypedef
Potrebbe essere, ho sentito la domanda. Non ho visto se stesso. Ma di sicuro non c'erano funzioni come il decremento. – fiz
È possibile avere numeri negativi? –