Master informatique, semestre 1
Modèles de calcul, devoir 2005

Exercice 1 : fonctions primitives récursives

Un corrigé est disponible ci-dessous.

Les fonctions primitives récursives sont des fonctions de plusieurs variables (entières), à valeurs entières. Elles sont définies comme suit :

  1. Montrer que la fonction constante égale à 3 est primitive récursive.
  2. Montrer que la fonction définie par :

    add ( 0 , y ) = y
    add ( x + 1, y ) = succ ( add ( x, y ) )

    est primitive récursive : on indiquera soigneusement quelles sont les fonctions g et h du schéma de récursion, et pourquoi elles sont primitives récursives.

  3. Donner un schéma de récursion qui prouve que la fonction mul (multiplication) est primitive récursive.
  4. Donner un schéma de récursion qui prouve que la fonction pred (prédécesseur) est primitive récursive. Note : le prédécesseur de 0 vaut 0.
  5. Donner un schéma de récursion qui prouve que la fonction sub (soustraction) est primitive récursive. Note : sub (x, y) vaut 0 si x < y.
  6. Montrer que les opérateurs de comparaison peuvent être définis à partir de la fonction sub, et sont donc primitifs récursifs.
  7. Montrer que si f1 et f2 sont primitives récursives, alors la fonction f définie par :

    f ( x, y ) = f1 ( x, y ) si x < y
    f ( x, y ) = f2 ( x, y ) sinon

    est primitive récursive.

Exercice 2 : machines de Turing

Partie I.

Un corrigé est disponible ci-dessous.

  1. On suppose que l'alphabet comporte quatre caractères : le caractère blanc, les chiffres binaires 0 et 1, et le caractère x. La bande comporte la représentation binaire d'un entier n lorsque la machine de Turing démarre.

    Ecrire les règles d'une machine M qui, à partir de cette configuration initiale, écrit exactement n caractères x sur la bande, à droite de la représentation de n.

    Note : ne pas introduire de caractère supplémentaire pour construire M. Il existe une solution avec seulement deux états, en supposant que la tête de lecture est positionnée initialement sur le chiffre le plus à droite de n — on ne demande pas que la représentation de n soit préservée par M.

  2. On suppose maintenant que l'alphabet comporte seulement deux caractères, notés a et b ; a est le caractère "blanc", c'est-à-dire celui qui remplit toute la bande, à l'exception d'une partie finie de celle-ci.

    On code chacun des quatre caractères de la question précédente par deux caractères du nouvel alphabet, comme suit : le caractère blanc est codé aa (on n'a pas le choix, expliquer pourquoi) ; 0 est codé ba, 1 est codé bb, et x est codé ab.

    Ecrire les règles d'une machine M' qui simule M. Par exemple, si n vaut 13 (représentation binaire 1101), la machine M' démarre avec bbbbbabb écrit sur les cases 1 à 8 de la bande (les autres cases contiennent le caractère a), et le calcul s'arrête avec ab répété 13 fois, sur les cases 9 à 34. Comme précédemment, on ne spécifie rien sur le contenu des cases 1 à 8 en fin de calcul (ni sur la position finale de la tête de lecture), mais on suppose qu'au départ la tête de lecture est située juste à droite de la représentation de n, c'est-à-dire ici sur la case 9.

  3. De façon générale on considère la simulation d'une machine T, qui utilise un alphabet de taille 2k, par une machine T ', qui utilise un alphabet binaire. En analysant comment simuler une règle de T, donner une estimation raisonnable du nombre d'états de T ' en fonction du nombre d'états de T ; idem pour le nombre de règles.

Partie II.

Un corrigé est disponible ci-dessous.

L'objet de cette partie est de démontrer que la fonction castor croît plus vite que toute fonction calculable ; en particulier la fonction castor n'est pas calculable. On rappelle qu'on considère les machines à n états, sur un alphabet binaire, qui sera ici composé des caractères a (blanc) et b (comme dans la partie I), avec une configuration initiale vide (autrement dit blanche), et que castor (n) désigne le nombre maximal de caractères non blancs (ici b) écrits sur la bande lorsqu'une telle machine s'arrête (voir le site d'Heiner Marxen pour tous les détails sur les castors — busy beavers). Cette fonction est manifestement croissante : en augmentant le nombre d'états, on augmente la classe de machines à examiner.

Soit f une fonction calculable, et F une machine de Turing qui calcule cette fonction : à partir d'une représentation binaire de n, cette machine calcule une représentation binaire de f (n), qui se trouve donc écrite sur la bande lorsque la machine s'arrête. On peut supposer pour simplifier que rien d'autre n'est écrit sur la bande lorsque la machine s'arrête (expliquer pourquoi), par contre il est très vraisemblable que la machine, pendant son calcul, utilise d'autres caractères que 0, 1, et le caractère blanc ; mais en utilisant les idées de la partie I, on peut coder l'alphabet de F avec l'alphabet binaire { a, b } (en codant chaque caractère de l'alphabet initial par un bloc de k caractères binaires), et simuler F avec une machine comportant plus d'états et de règles, mais travaillant uniquement avec cet alphabet binaire.

Dans la suite on suppose donc que la machine F utilise l'alphabet binaire { a, b }. On construit une nouvelle machine G comme suit :

Le nombre d'états de G est la somme des nombres d'états des machines utilisées pour chacune des trois étapes, soit :

γ (n) = λ (n) + α + β

où les constantes α et β désignent respectivement le nombre d'états de F et celui de M', tandis que λ (n) désigne le nombre d'états nécessaires pour la première étape, qui dépend de n, ou plus précisément du nombre de chiffres de la représentation binaire de n ; enfin γ (n) désigne le nombre d'états de G.

  1. Montrer qu'on a : f (n) < castor ( γ (n) ). En déduire :

    γ (n) < nf (n) < castor (n) .

  2. Donner une estimation raisonnable de λ (n), et dessiner l'allure de la fonction γ (n). En déduire que, dès que n est suffisamment grand, on a : γ (n) < n ; une preuve mathématique exacte est bienvenue, mais n'est pas exigée.
  3. Les deux questions précédentes prouvent que, pour toute fonction calculable f, castor (n) finit par dépasser f (n) ; expliquer par contre pourquoi on ne peut pas espérer avoir :

    n , f (n) < castor (n) .

    Montrer aussi que pour toute constante N (par exemple N = 1000), il existe des fonctions calculables f telles que f (N) > castor (N), bien que par exemple on ne connaisse pas la valeur (gigantesque) de castor (1000).

Exercice 3 : listes

Un corrigé est disponible ci-dessous.

On souhaite coder en λ-calcul les listes, au sens du langage LISP. Toute liste est construite par l'opérateur cons, et cons A B est la liste obtenue en ajoutant A en tête de la liste B (le second argument de cons est toujours une liste). Il y a une seule exception : la liste vide notée nil ; la liste à un seul élément A, notée ( A ), est égale à cons A nil, etc.

On rappelle que le λ-terme pair, qui permet de construire des paires (couples), et les projections first et second sont définis par :

pair = λ x y f . f x y
first = λ p . p true
second = λ p . p false

  1. Représenter la liste ( ( A B ) C ) à l'aide de l'opérateur cons.
  2. On définit cons = λ x y . pair false ( pair x y ). Ecrire les termes head et tail tels que :

    head ( cons A B ) → A
    tail ( cons A B ) → B

    Réduire les réponses en forme normale.

  3. On définit isnull (opérateur qui teste si une liste est vide) par isnull = first, car ainsi :

    isnull ( cons A B ) → false

    Donner la définition la plus courte possible de nil, de telle sorte que :

    isnull niltrue

    Note : la réponse évidente nil = pair true … n'est pas celle demandée.

Corrigé

Exercice 1

Voir l'énoncé ci-dessus.

  1. La fonction c1 constante égale à 1 est la composée des fonctions primitives récursives succ et zero : elle est donc primitive récursive. La fonction c2 constante égale à 2 est la composée des fonctions primitives récursives succ et c1 : elle est donc primitive récursive ; et ainsi de suite.

  2. La fonction h du schéma de récursion est la fonction identité (à une variable), qui peut être vue comme la projection à une variable π1 (x) = x , qui est primitive récursive. La fonction g est définie par :

    g ( x, y, z ) = succ ( π3 ( x, y, z ) ) ;

    elle est primitive récursive, car c'est la composée de fonctions primitives récursives.

  3. Schéma de récursion pour mul :

    mul ( 0 , y ) = 0
    mul ( x + 1, y ) = add ( mul ( x, y ) , y )

    La fonction h du schéma de récursion est la fonction zero. La fonction g est la composée de add et des projections π3 et π2 ; comme add est primitive récursive (question précédente), mul l'est aussi.

  4. Schéma de récursion pour pred :

    pred ( 0 ) = 0
    pred ( x + 1 ) = x

    La fonction g du schéma de récursion est simplement la projection π1 :

    pred ( x + 1 ) = π1 ( x , pred (x) ) = x .

    C'est une application correcte du schéma de récursion, bien que la définition de pred (x + 1) ne fasse pas intervenir explicitement pred (x) — ce qui a troublé certains étudiants, qui ont préféré :

    pred ( 0 ) = 0
    pred ( x + 1 ) = succ ( pred (x) )

    Hélas cette définition est fausse : la fonction qui vérifie ce schéma de récursion est … l'identité.

  5. Soit subx définie par :

    subx ( x , y ) = y - x si x < y ( 0 sinon ).

    Voici un schéma de récursion pour subx :

    subx ( 0 , y ) = y
    subx ( x + 1 , y ) = pred ( subx ( x , y ) )

    Quant à sub, définie par :

    sub ( x , y ) = x - y si x > y ( 0 sinon )

    on peut la voir comme la composée subx ( π2 ( x , y ) , π1 ( x , y ) ). En d'autres termes, l'ordre des arguments est sans importance pour déterminer si une fonction est primitive récursive.

  6. Les opérateurs de comparaison utilisent la fonction sub, mais on a besoin d'une fonction égale à 1 pour tout entier positif (strictement). Il y a deux solutions :

    iszero ( x ) = sub ( 1, x )
    positif ( x ) = iszero ( iszero ( x ) ) = sub ( 1 , sub ( 1, x ) )

    On remarque au passage que iszero sert aussi à coder la négation. Une autre solution est de donner un schéma de récursion, par exemple :

    positif ( 0 ) = 0
    positif ( x + 1 ) = 1

    d'où les définitions :

    x > y gt ( x , y ) = positif ( sub ( x , y ) )
    xy ge ( x , y ) = gt ( succ ( x ) , y )

    On peut donner des définitions analogues pour les opérateurs < (lt) et ≤ (le), ou utiliser la négation, mais le plus simple est d'échanger x et y :

    x < y lt ( x , y ) = gt ( y , x )
    xy le ( x , y ) = ge ( y , x )

    Reste l'égalité ; le plus simple est de multiplier les opérateurs le et ge, car la multiplication code la conjonction (opérateur and). Pour l'inégalité, on peut utiliser la négation iszero, ou directement l'addition, qui code (presque) la disjonction (opérateur or) :

    x = y eq ( x , y ) = le ( x , y ) * ge ( x , y )
    xy ne ( x , y ) = iszero ( eq ( x , y ) ) =
    positif ( lt ( x , y ) + gt ( x , y ) )

    en employant les notations usuelles pour l'addition et la multiplication, qui sont primitives récursives (questions 2 et 3).

  7. On peut définir f par :

    f ( x, y ) = f1 ( x, y ) * lt ( x , y ) + f2 ( x, y ) * ge ( x , y )

    Une autre solution (due à Saad El Ghissassi, félicitations) est de définir l'opérateur if par un schéma de récursion, en s'inspirant du λ-calcul (où true — resp. false — est un opérateur qui sélectionne son premier — resp. second — argument) :

    if ( 0, y, z ) = z
    if ( x + 1 , y, z ) = y

    d'où tout simplement :

    f ( x, y ) = if ( lt ( x , y ) , f1 ( x, y ) , f2 ( x, y ) ).

    Note : on peut évidemment remplacer lt par n'importe quel prédicat primitif récursif, ce qui justifie que les définitions par cas sont valides dans la classe des fonctions primitives récursives.

Annexe et références. Les fonctions primitives récursives sont calculables, mais ce sont des fonctions totales, donc les fonctions calculables partielles ne sont certainement pas primitives récursives. Pire, Ackermann a construit une fonction calculable totale non primitive récursive — la définition de la fonction d'Ackermann A ( m, n ) est simple, mais démontrer qu'elle n'est pas primitive récursive est beaucoup plus difficile (en fait Ackermann a montré que, sur la diagonale, A ( n, n ) croît plus vite que toute fonction primitive récursive).

Pour obtenir un modèle de calcul équivalent à celui des machines de Turing, au λ-calcul, etc. il faut ajouter un schéma supplémentaire de minimisation ; voir par exemple l'article sur les fonctions récursives dans l'encyclopédie Wikipedia ; pour éviter les ambiguïtés, ces fonctions sont aussi appelées μ-récursives.

Le modèle de calcul des fonctions récursives date, comme les autres, des années 1930 ; il est important, car il ne fait pas intervenir explicitement de notion de machine, et pour montrer qu'une classe Γ de fonctions englobe toutes les fonctions récursives (et donc toutes les fonctions calculables, d'après la thèse de Church), il suffit de montrer que la fonction zero, la fonction succ et les projections sont dans la classe Γ — ce qui en général n'est guère difficile — puis que Γ est stable pour chacun des trois schémas : composition, récursion primitive, et minimisation. C'est ainsi qu'on montre que les machines de Turing sont capables de calculer toutes les fonctions récursives, ou que toute fonction récursive est λ-définissable.

Exercice 2, partie I

Voir l'énoncé ci-dessus.

  1. Voici une solution pour la machine M, avec deux états notés 10 (état initial) et 20. L'état 10 sert à décrémenter n, en remplaçant …10…0 par …01…1 ; l'état 20 sert à ajouter un x en fin de bande (vers la droite). La machine s'arrête lorsque n devient nul, c'est-à-dire lorsque, dans l'état 10, en se déplaçant vers la gauche, M atteint un caractère blanc sans avoir rencontré de 1.

    10 0 10 1 G
    10 1 20 0 D
    10 x 10 x G
    
    20 blanc 10 x G
    20 0 20 0 D
    20 1 20 1 D
    20 x 20 x D
    

    L'absence de règle pour l'état 10, lorsque le caractère lu est blanc, provoque l'arrêt de la machine. Les trois dernières règles peuvent être abrégées en une seule :

    20 - 20 - D
    

    qui se lit ainsi : dans les autres cas, rester dans l'état 20, ne pas modifier le caractère lu, et déplacer la tête vers la droite.

  2. Notons d'abord que le caractère blanc occupe toute la bande de la machine M, à l'exception d'une portion finie de celle-ci, et doit donc être codé aa, puisque, en dehors d'une portion finie, la bande de la machine M' ne contient que des a.

    Voici une solution pour la machine M' ; l'état intial 0 et l'état 1 servent à déplacer la tête de deux caractères vers la gauche, et le tiret signifie "autres cas" (ou "caractère quelconque") lorsqu'il remplace le caractère lu, et "ne pas modifier le caractère lu" lorsqu'il remplace le caractère écrit. Cette solution lit toujours les blocs de deux caractères de la gauche vers la droite, ce qui en facilite la généralisation (question suivante). Par contre, en adaptant le sens de lecture des blocs au déplacement de la tête, on peut fabriquer une machine plus concise (voir plus loin).

    0 - 1 - G
    1 - 10 - G
    
    10 a 100 - D
    10 b 110 - D
    
    // simulation de la règle 
    // 10 x 10 - G
    
    100 b 101 - G
    101 - 102 - G
    102 - 10 - G
    
    // simulation de la règle 
    // 10 0 10 1 G
    
    110 a 111 b G
    111 - 112 - G
    112 - 10 - G
    
    // simulation de la règle 
    // 10 1 20 0 D
    
    110 b 20 a D
    
    20 a 200 - D
    20 b 210 - D
    
    // simulation de la règle 
    // 20 blanc 10 x G
    
    200 a 201 b G
    201 - 202 - G
    202 - 10 - G
    
    // simulation de la règle 
    // 20 - 20 - D
    
    200 b 20 - D
    210 - 20 - D
    

    L'état 10 (resp. 20) est dédoublé en deux états 100 et 110 (resp. 200 et 210), selon le premier caractère lu. Lorsque, dans l'état 100, la machine M' lit le caractère b, la situation est la même que lorsque, dans l'état 10, la machine M lit le caractère x : il faut donc revenir dans l'état 10, sans modifier les deux derniers caractères lus (à savoir ab, qui code x), et déplacer la tête vers la gauche trois fois (au lieu d'une) pour la positionner au début du précédent bloc de deux caractères ; d'où les états supplémentaires 101 et 102. Et ainsi de suite…

    En modifiant légèrement M (tant que la tête se déplace à gauche à la recherche du chiffre 1, on ne modifie pas les chiffres 0, qu'on remplace par 1 "au retour"), on peut construire une machine plus concise, qui exploite les particularités de la machine M à simuler ; dans cette version, l'état initial est numéroté 10, et la tête est positionnée sur le dernier caractère de n.

    // déplacement vers la gauche
    
    10 a 100 - G
    10 b 110 - G
    
    // simulation de la règle 
    // 10 0 10 0 G
    
    100 b 10 - G
    
    // simulation de la règle 
    // 10 1 20 0 D
    
    110 b 111 b D
    111 b  20 a D
    
    // simulation de la règle 
    // 10 x 10 - G
    
    110 a 10 - G
    
    // déplacement vers la droite
    
    20 a 200 - D
    20 b 210 - D
    
    // simulation de la règle 
    // 20 0 20 1 D
    
    210 a 20 b D
    
    // simulation de la règle 
    // 20 x 20 - D
    
    200 b 20 - D
    
    // simulation de la règle 
    // 20 blanc 10 x G
    
    200 a 201 b G
    201 a  10 - G
    

    Il n'y a pas de règle pour l'état 100, lorsque le caractère lu est a : la machine s'arrête (la recherche du chiffre 1 vers la gauche a échoué, on a lu le caractère blanc, codé aa). Il n'y a pas de règle pour l'état 210, lorsque le caractère lu est b : le cas ne se produit jamais (dans cette version, la machine M ne rencontre jamais le chiffre 1, codé bb, lorsque la tête se déplace vers la droite).

    Des étudiants ont remarqué qu'on peut du coup remplacer l'état 111 par 210 ; d'autre part l'état 201 peut être manifestement remplacé par 110 (la règle est la même), ce qui fait gagner deux états et une règle : la machine finale obtenue possède 6 états et 11 règles.

  3. Pour simuler une règle : q x q' x' δ , la machine T ' doit commencer par lire le bloc de k symboles binaires qui code le symbole x. Pour un état donné q, il peut exister autant de règles que de symboles lus x ; T ' a donc besoin de 2k états intermédiaires [ q, u ], où u désigne un mot binaire de taille inférieure à k, avec les règles associées :

    [ q, u ] , a , [ q, u a ] , - , D
    [ q, u ] , b , [ q, u b ] , - , D

    pour une lecture de gauche à droite — on peut utiliser aussi des états similaires pour une lecture de droite à gauche, mais ce n'est pas indispensable. Par exemple pour k = 4, un état q sera dupliqué en 16 états :

    q = [ q, ε ] , [ q, a ] , [ q, b ] , [ q, a a ] , [ q, a b ] , … , [ q, bbb ] .

    De même T ' a besoin de 2k états intermédiaires [ u, q' ] pour écrire le symbole x' (de droite à gauche), avec les règles correspondantes, symétriques de celles utilisées pour lire un symbole. Supposons par exemple que le symbole lu soit x = a a b a, et que le symbole écrit soit x' = b a b b ; la règle de T sera simulée comme suit :

    q a [ q, a ] - D
    [ q, a ] a [ q, a a ] - D
    [ q, a a ] b [ q, a a b ] - D
    [ q, a a b ] a [ b a b, q' ] b G
    [ b a b, q' ] - [ b a, q' ] b G
    [ b a, q' ] - [ b, q' ] a G
    [ b, q' ] - q' b

    Reste à déplacer la tête de k cellules vers la droite ou vers la gauche, selon ce qui est spécifié dans la règle de T en cours de simulation. On s'aperçoit au passage qu'on a omis de conserver en mémoire le sens de ce déplacement : un état [ u, q' ] doit incorporer cette information, à l'aide d'un troisième champ, qui contient G (déplacement à gauche dans la règle initiale) ou D (déplacement à droite dans la règle initiale) ; ce qui mutiplie par 2 le nombre d'états correspondants. Enfin on a besoin d'environ 2 k (en fait 2 k - 4) états supplémentaires, notés [ q , i ] (où i désigne un entier positif ou négatif, inférieur ou égal en valeur absolue à k - 2), pour réaliser le déplacement de la tête au début du bloc suivant (ou précédent). Avec ces compléments, voici la simulation de la règle q x q' x' G (où x est codé par a a b a, et x' par b a b b) :

    q a [ q, a ] - D
    [ q, a ] a [ q, a a ] - D
    [ q, a a ] b [ q, a a b ] - D
    [ q, a a b ] a [ b a b, q' , G ] b G
    [ b a b, q' , G ] - [ b a, q' , G ] b G
    [ b a, q' , G ] - [ b, q' , G ] a G
    [ b, q' , G ] - [ q', G ] b G
    [ q' , G ] - [ q', -1 ] - G
    [ q' , -1 ] - [ q', -2 ] - G
    [ q' , -2 ] - q' - G

    Soit n le nombre d'états de T, et n' le nombre d'états de la machine T ' que nous venons de construire ; on a :

    n' = n * ( 3 * 2k + 2 * k - 4)

    Soit r le nombre de règles de T et r' le nombre de règles de T ' ; l'analyse de l'exemple ci-dessus montre qu'une règle de T est simulée par

    k + 2 (k - 1) = 3 k - 2

    règles de T ' (en admettant les regroupements de règles : on ne tient pas compte du caractère lu lors des phases d'écriture et de simple déplacement). Mais ce n'est pas le rapport r' / r , car des simulations de règles différentes (machine T ) peuvent utiliser des règles communes (machine T ' ) ; pour évaluer correctement ce rapport, il faut se rappeler que pour une machine déterministe, le nombre de règles est borné par le nombre d'états multiplié par la taille de l'alphabet. D'où les formules suivantes, qui sont approximatives (des règles peuvent manquer, car inutiles, et d'autres peuvent être regroupées, car indépendantes du symbole lu) :

    r = 2k n , r' = 2 n'

    ce qui donne approximativement r' = 6 r, dès que k est petit devant 2k. Ce résultat est assez surprenant : la taille de la machine T ' n'est pas beaucoup plus élevée que celle de la machine T, et ceci indépendamment de k.

Exercice 2, partie II

Voir l'énoncé ci-dessus.

  1. Avant lancement de la machine G la bande est vide (blanche) ; lorsque G s'arrête, la bande contient le code du chiffre 1, répété f (n) fois. Comme le code du chiffre 1 contient au moins un caractère b, la machine G figure dans la compétition des machines avec γ (n) états, et son "score" f (n) est inférieur au record (par définition d'un record), d'où la relation demandée :

    f (n) < castor ( γ (n) )

    Note : l'inégalité est stricte, car il est très peu vraisemblable que G soit la machine "record". Accessoirement, la bande contient aussi, en fin d'exécution, une suite de chiffres (codés sur l'alphabet { a, b } ) tous égaux à 0 (ou à 1, selon l'algorithme choisi pour la machine M de la partie I) à la place de la représentation initiale de n. Un autre argument est qu'on peut décider que le code du chiffre 1 comporte au moins deux caractères b.

    Comme la fonction castor est croissante, on déduit de l'inégalité précédente :

    γ (n) < nf (n) < castor (n) .

  2. Le nombre d'états nécessaires pour écrire n est du même ordre de grandeur que le nombre de chiffres binaires de n, et chacun de ces chiffres est codé sur un bloc de k caractères de l'alphabet { a, b }, d'où :

    λ (n) = k log2 (n)

    où le logarithme binaire est arrondi par excès à l'entier le plus proche. La fonction γ (n) est donc une fonction logarithmique, avec une translation vers le haut due à la constante α + β. Une telle fonction devient inférieure à n pour n assez grand, car :

    lim γ (n) / n = k * lim log (n) / n + lim (α + β) / n = 0.

  3. On connaît par exemple castor (4) = 13, et il existe une infinité de fonctions calculables f telles que f (4) > 13. La situation est la même pour castor (1000) : bien qu'on ne connaisse pas la valeur de ce nombre (et on ne le connaîtra certainement jamais), cette valeur existe ; comme l'ensemble des entiers est infini, il existe une infinité de fonctions calculables qui passent au-dessus de cette valeur pour n = 1000…

Exercice 3 : listes.

Voir l'énoncé ci-dessus.

  1. La liste ( ( A B ) C ) est construite ainsi :

    cons ( cons A ( cons B nil ) ) ( cons C nil )

  2. Une liste est codée par une double paire, d'où :

    head = λ l . first ( second l )
    tail = λ l . second ( second l )

    Oublier les parenthèses est une grosse faute ; certains proposent head = first second, ce qui est la même (grosse) erreur. En remplaçant first et second par leurs définitions, on obtient :

    head = λ l . first ( ( λ p . p false) l )
    → λ l . first ( l false) = λ l . ( λ p . p true) ( l false)
    → λ l . l false true

    Ce dernier terme est irréductible (remplacer false et true par leurs valeurs n'y change rien). De même :

    tail → λ l . l false false

  3. On a :

    isnull nil = first nil = ( λ p . p true ) nilnil true

    donc le plus simple est de choisir nil = I = λ x . x .