2015-12-03 17 views
5

Sto cercando di costruire sottrazione, addizione, divisione, moltiplicazione e altre operazioni utilizzando solo seguenti:Sottrazione operazione utilizzando solo incremento, cappio, assegnare zero

  1. incr (x) - Una volta che questa funzione è chiamato assegnerà x + 1 a x
  2. assign (x, y) - Questa funzione assegnerà il valore di y a x (x = y)
  3. zero (x) - Questa funzione assegnerà 0 a x (x = 0)
  4. ciclo X {} - le operazioni scritte tra parentesi verranno eseguite X volte

Utilizzando seguenti norme, è semplice da implementare aggiunta (add) come questo:

ADD (x, y) { 
loop X { 
    y = incr (y) 
} 
return y 
} 

Tuttavia, sto lottando per implementare sottrazione. Penso che tutte le altre operazioni necessarie potrebbero essere completate utilizzando la sottrazione.

Qualsiasi suggerimento sarà molto apprezzato.

+1

Sei sicuro che sia possibile? Sembra che qualsiasi nuovo valore che crei sia una costante fissa o una funzione affine positiva degli input. – templatetypedef

+0

Potrebbe essere, ho sentito la domanda. Non ho visto se stesso. Ma di sicuro non c'erano funzioni come il decremento. – fiz

+0

È possibile avere numeri negativi? –

risposta

5

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:

  1. 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.

  2. Quando x è 0 corriamo il ciclo 0 volte (cioè mai) e poi abbiamo semplicemente tornare y = 0.

  3. 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.

+2

È un'ottima spiegazione! Vorresti dire come controllare l'uguaglianza di due variabili usando solo le operazioni date? - @Aadit M Shah – korujzade

+0

@koruj È certamente possibile. Se lo pubblichi come una domanda, ti fornirò una risposta. –

+1

@korujzade Ho risposto alla tua domanda qui: http://stackoverflow.com/questions/34829670/relational-operations-using-only-increment-loop-assign-zero?lq=1 –