2009 December

Archive for December, 2009

Exercise 1.10

Tuesday, December 29th, 2009

Given the following implementation of the Ackermann’s Function:

1
2
3
4
5
6

(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))

What are the evaluations of these expressions:

(A 1 10)

Value: 1024

(A 2 4)

Value: 65536

(A 3 3)

Value: 65536

What are the mathematical counterparts of these procedures:

1	(define (f n) (A 0 n))

corresponds to: $f(n)=2n$

1
2
3
4
5
6
7
8

(define (g n) (A 1 n))

(A 0 (A 1 (- n 1))
(A 0 (A 0 (A 1 (- n 2))))
(A 0 (A 0 (A 0 (A 1 (- n 3)))))
.
.
.

corresponds to:

$g(n) = \begin{cases}0 & \mbox{if }n=0 \\ 2^n & \mbox{if }n \ge 1\end{cases}$

1
2
3
4
5
6
7
8
9

(define (h n) (A 2 n))

(A 2 n)
(A 1 (A 2 (- n 1)))
(A 1 (A 1 (A 2 (- n 2))))
(A 1 (A 1 (A 1 (A 2 (- n 3)))))
.
.
.

At some step i, the most inner combination in the form (A 2 (- n i)) will evaluate to 2 cause n-i=1. (A 1 x) is 2^x by the definition of g(n), and there will be n evaluations of such combination, resulting in:

$2^{2^{2^{\dots}}}$

This can be also expressed as a recurrence:

$h(n) = \begin{cases}0 & \mbox{if }n=0 \\ 2 & \mbox{if }n=1 \\ 2^{h(n-1)} & \mbox{if }n \ge 2\end{cases}$

Posted in Computer Science | No Comments »

Exercise 1.9

Monday, December 28th, 2009

Evaluate (+ 4 5) using the following procedure definition:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

This is a linear recursive process.

Now, use the following definition instead to evaluate the same combination:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9

This is an linear iterative process.

Posted in Computer Science | No Comments »

Induction

Saturday, December 26th, 2009

Induction is a reasoning method to demonstrate true properties for the natural numbers:

$\mathbb{N}={0, 1, 2,...}$
In Computer Science, this is widely used since a lot of entities can be mapped to them.
To illustrate the process through an example, say we are given the following proposition -something that is either true or false:

Proposition. $Let\; p(n) ::= n^2 + n + 41$

$\forall n\!\in\!\mathbb{N},\; p(n)\; is\; prime.$
That is our proposition $P(n)$ . To that end, we may calculate the successive values of $p(n)$ :
$\begin{array}{lcl}p(0)=41\;is\;prime \\p(1)=43\;is\;prime \\p(2)=47\;is\;prime \\p(3)=53\;is\;prime \\p(4)=61\;is\;prime \\\vdots\end{array}$
If we continue to calculate the values for $p(n)$ for bunch of values we may believe that the proposition is true. Alas, you can’t conclude that:

$\forall n\!\in\!\mathbb{N}\ P(n)$

holds true because verifying an assertion for a finite set of values doesn’t prove anything for the whole infinite set of $\mathbb{N}$ , no matter the amount of values checked. As a point in case:

$p(40)=40^2+40+41=40(40+1)+41=41(40 + 1) = 41^2$
which is clearly not prime.

Example: A true proposition

We have to demonstrate by induction that:

$P(n)::=\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{n(n+1)}=\frac{n}{n+1}$

First, let’s remove the ellipses and use a summation to represent the formulation:

$P(n)::=\sum_{k=1}^n \frac{1}{k(k+1)}=\frac{n}{n+1}$

Induction hypothesis: P(n)
Basis step: $P(1)::=\frac{1}{2}=\frac{1}{2}$
Inductive step:
$\begin{array}{lcl}\forall n\!\in\mathbb{N} \ P(n)\to P(n+1) \\ \\P(n+1)::=\overbrace {\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{n(n+1)}}^{P(n)}+\frac{1}{(n+1)(n+1+1)}=\frac{n+1}{n+2} \\ \\P(n+1)::= \frac{n}{n+1}+\frac{1}{(n+1)(n+2)}=\frac{n+1}{n+2}\\ \\P(n+1)::= \frac{n(n+2)+1}{(n+1)(n+2)}=\frac{n+1}{n+2}\\ \\P(n+1)::= n(n+2)+1 = (n+1)^2\\ \\P(n+1)::= n^2+2n+1 = n^2+2n+1\end{array}$

We just used a basic inference rule named modus ponens: if $p$ is true and $p \to q$ is true, then $q$ is true, also written:

$\frac{p, \;p \to q}{q}$

Therefore, the Induction Axiom can be expressed as:

$\frac{P(0),\;\forall m\in\mathbb{N}\;P(m) \to P(m+1)}{\forall n\in\mathbb{N} \ P(n)}$

Demonstrating the Induction Axiom

But, how can we demonstrate the Induction Axiom itself? To that end, we can use reduction to the absurd:

Hypothesis: $P(N)$ is not true for every $n\in\mathbb{N}$ , i.e. there are natural numbers for which the proposition is false.
Using the Well-Ordering Principle of the natural numbers, we can state:
$\exists\;n^{*}\in\mathbb{N} \/\ is\ the\ smallest\ among\ the\ ones\ not\\ satisfying\ the\ proposition$
$P(1)$ is true by induction $\Leftrightarrow n^{*} \neq 1 \Rightarrow P(n^{*}-1)$ is true.
(If $n^{*}$ is not 1, then $P(n^{*}-1)$ must be true because $n^{*}$ is the smallest of all the natural numbers for which the proposition is false.)
$P(n^{*}-1)$ is true $\Rightarrow P(n^{*})$ is true by induction.
$P(n^{*})$ is true by induction, but at the same time $P(n^{*})$ is false by 2. Hence, the initial hypothesis must be false.

References

Mathematics for Computer Science at MIT OpenCourseWare

Tags:maths
Posted in Computer Science | 1 Comment »

Exercise 1.8

Thursday, December 24th, 2009

Use the following approximation to calculate the cube root using the Newton’s Method:

$\frac{x/y^2 + 2y}{3}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(define (square x) (* x x))

(define (cube x) (* x x x))

(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.0000001))

(define (improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (cubert-iter guess x)
(if (good-enough? guess x)
guess
(cubert-iter (improve guess x)
x)))

1	(cubert-iter 1 9)

Value: 2.0800838230519042806950087

1	(cubert-iter 6.8 8)

Value: 2.0000000000010389297385368

Tags:scheme, sicp
Posted in Computer Science | No Comments »

Exercise 1.7

Wednesday, December 23rd, 2009

Given this procedure:

1 2	(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))

We want an improved version of good-enough? that implements the following check:

$|guess_{n+1} - guess_{n}| < \frac{guess_{n+1}}{k}$
for a value of $k=10^5$ .

1
2
3
4
5
6
7

(define (good-enough-improv? oldguess newguess)
(< (abs (- newguess oldguess)) (/ newguess 10000)))

(define (sqrt-iter-improv oldguess newguess x)
(if (good-enough-improv? oldguess newguess)
newguess
(sqrt-iter-improv newguess (improve newguess x) x)))

Tags:scheme, sicp
Posted in Computer Science | No Comments »

Exercise 1.6

Monday, December 21st, 2009

Given this new definition of the if special form:

1
2
3

(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))

It is used in the following program:

1
2
3
4
5

(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))

What happens is that the operands of the new-if are evaluated, which means that the computation will not finish due to a recursive invocation chain of the sqrt-iter procedure, as illustrated here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

(sqrt 4)

(sqrt-iter 1.0 4)

(new-if (good-enough? 1.0 4)
4
(sqrt-iter (improve 1.0 4)
4)))
(new-if #f
4
(new-if (good-enough? 2.5 4)
2.5
(sqrt-iter (improve 2.5 4)
4)))
(new-if #f
4
(new-if #f
2.5
(new-if (good-enough? 2.05 4)
2.05
(sqrt-iter (improve 2.05 4)
4)))
.
.
.

Tags:scheme, sicp
Posted in Computer Science | No Comments »

Exercise 1.5

Sunday, December 20th, 2009

Given the following two procedures:

1
2
3
4
5
6

(define (p) (p))

(define (test x y)
(if (= x 0)
0
y))

What is the result of evaluating

1	(test 0 (p))

using the following two substitution models.

Applicative-order evaluation evaluates all the expression arguments and then applies:

1
2
3
4
5

(test 0 (p))
(test 0 (p))
.
.
.

The evaluation enters into an infinite loop since the second expression argument is evaluated to itself.

Normal-order evaluation substitutes operand expressions for parameters until it obtains an expression involving only primitive operators:

1
2
3
4
5
6
7
8
9

(test 0 (p))

(if (= 0 0)
0
(p))

(if #t 0 (p))

0

Value: 0

TICS

Archive for December, 2009

Exercise 1.10

Exercise 1.9

Induction

Exercise 1.8

Exercise 1.7

Exercise 1.6

Exercise 1.5

Categories

Archives

Pages