Subject: [SWIPL] problem

From: "dhruv malik" <[email-masked]>
Date: 2 Mar 2002 05:53:49 -0000

from Computational Intelligence by david pool Ex3.10 pg 108

Q) Use a binary representation of natural numbers,where a number 
is either one,b(N,zero), or b(N,one),where

one denotes the number 1.
b(N,zero) denotes the number 2*N1 where N1 is the number denoted 
by N.
b(N,one) denotes the number 2*N1+1 where N1 is the number denoted 
by N.

For ex,b(one,one)denotes binary 11 which is 3,b(b(one,one),zero) 
denotes binary 110 or 6,and b(b(b(one,one),zero),one) denotes 
binary 1101 or 13.
        Define the following predicates,such that all the 
operations are linear in size of the representation, and not 
linear in the size of the numbers:

a)number(N) is true if N is the form of a number.

b)succ(N,M) is true if M is the number after number N.

c) plus(X,Y,Z)is true if the number denoted by z is the sum of the 
number denoted by X and Y(Z=X+Y).

d) times(X,Y,Z) is true if Z is the product of number X and Y.

e) is(V,E) which is a relation between a number V and an 
arithmetic expression E,is true if V is the value of expression E. 
An expression can be a number or of the form X+Y,X*Y orX-Y where X 
and Y are expressions. This is often written as V is E.

f) Define the relation lt(N,M) that is true if number N is less 
than number M. This is often written as N<M.

g) Define the relation neq(N,M) that is true if number N and M are 
different numbers. This is often written as N/=M.(HINt use result 
 from (f)).

h) Suppose someone suggested extending this representation to all 
non negative integers simply by adding zero as a number. Why might 
this cause problem? Hint: Consider b(zero,one).