Trouver la "définition mathématique concise" d'une fonction dans SICP

Question

Structure and Interpretation of Computer Programs donne cette implémentation de la fonction d'Ackermann :

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

L'exercice 1.10 demande les "définitions mathématiques concises" des fonctions suivantes qui appellent A :

(define (f n) (A 0 n)) 
(define (g n) (A 1 n)) 
(define (h n) (A 2 n))

Les sorties de f et g pour les entiers 1 à 4 sont reconnaissables comme 2n et 2^n. Mais h est 2^(2^n-1), une formule que je n'ai pas pu reconnaître simplement en recherchant un modèle dans les sorties. Comment doit-on compléter cet exercice ? Existe-t-il une méthode pour dériver la notation mathématique, peut-être basée sur la notation de la fonction d'Ackermann ?

Answer 1

Après avoir déjà découvert que (f n) = (* 2 n) et (g n) = (expt 2 n), nous pouvons utiliser cette information ainsi que la définition de A pour déterminer ce que sera (A 2 n) :

En mettant x=2 :

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

En utilisant le fait que (A 1 n) = (expt 2 n)

(define (A2 y) 
  (cond ((= y 0) 0)
        ((= y 1) 2)
        (else (expt 2 (A2 (- y 1))))))

À partir de cela, vous pouvez voir plus clairement le schéma de récursion selon lequel A2 donne des puissances imbriquées de deux comme 2^(2^(2^2)). Je pense que votre réponse 2^(2^n-1) pourrait être incorrecte.

Answer 2

Vous pouvez utiliser le schéma lui-même pour trouver des réponses à ceci :

(define (*^ x y) `(* ,x ,y))

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

;> (A 0 100)
;'(* 2 100)
;> (A 0 234)
;'(* 2 234)

suggère que (A 0 n) = (* 2 n).

---

(define (*^ x y) `(* ,x ,y))

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

;> (A 1 10)
;'(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 2)))))))))
;> (A 1 5)
;'(* 2 (* 2 (* 2 (* 2 2))))

réorganisé les règles pour éviter une erreur. On peut voir qu'il fait *2 fois, donc 2^n.

---

(define (*^ x y) `(* ,x ,y))

(define (A x y)
  (cond ((= x 0) (*^ 2 y))
        ((= x 1) `(expt 2 ,y))
        ((= y 0) 0)
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

;> (A 2 5)
;'(expt 2 (expt 2 (expt 2 (expt 2 2))))
;> (A 2 6)
;'(expt 2 (expt 2 (expt 2 (expt 2 (expt 2 2)))))

Ceci confirme l'idée que nous obtenons une tour d'exposants.

Answer 3

Le livre a déjà introduit la méthode de substitution, il n'est donc pas faux de l'utiliser.

Commencez par (A 0 n)

Ceci est

(cond ((= n 0) 0)
      ((= 0 0) (* 2 n))
      ((= 0 1) 2)
      (else (A (- 0 1) (A 0 (- n 1)))))

qui est clairement 2n.

Ensuite, (A 1 n) est

(cond ((= n 0) 0)
      ((= 1 0) (* 2 n))
      ((= n 1) 2)
      (else (A (- 1 1) (A 1 (- n 1))))))

qui est

(A 0 (A 1 (- n 1)))

ou, profitant de l'étape précédente,

(* 2 (A 1 (- n 1))

C'est-à-dire,

A 1 n = 2 * (A 1 (n-1))
      = 2 * 2 * (A 1 (n-2))
      = ...

Puisque nous savons que A x 1 = 2 pour tous les x, nous voyons que

A 1 n = 2 * 2 * ... * 2

avec n facteurs, c'est-à-dire 2n.

Appliquant un raisonnement similaire au dernier cas laissé en exercice.