• Remarque : calcul et manipulation de symboles sont équivalents. Les entiers correspondent à des mots sur un alphabet, en unaire, base b, nombres romains…
• fonctions polynomiales telles P\left(x\right) = x^3 + 2 x^2 + x + 52 sont construites avec
  • des fonctions de base
  • des combinaisons de fonctions

Nous allons voir comment Alonzo Church a exploité ce paradigme pour analyser la construction de notre système de calcul sur les entiers.

• Fonctions de base
  • (a) zero_k : \mathbb{N}^k \rightarrow \mathbb{N}
    zero_k\left(n_1,n_2,\ldots n_k\right) = 0 \quad \forall n_1,n_2,\ldots n_k\in \mathbb{N}
  • (b) projecteurs : j^Ième k-projecteur
    • id_{k,j} : \mathbb{N}^k \rightarrow \mathbb{N}
    • id_{k,j}\left(n_1,n_2,\ldots n_k\right) \mapsto n_j
  • © successeur : succ : \mathbb{N} \rightarrow \mathbb{N}
    • succ : n \mapsto n+1
• Opérations sur les fonctions
  • (1) Composition
    • Soient m fonctions g_1, g_2, \ldots , g_m
    • g_i : \mathbb{N}^k \rightarrow \mathbb{N}
    • et une fonction f: \mathbb{N}^k \rightarrow \mathbb{N}
    • La composée de \left(g_1, g_2,\ldots , g_m\right) par f est définie par

      \underbrace{f \circ \left( g_1, g_2,\ldots , g_m\right)}_{\mathbb{N}^k \rightarrow \mathbb{N}} = f\left( g_1\left( n_1,n_2,\ldots , n_k\right), \ldots g_m \left( n_1,n_2,\ldots , n_k\right)\right)
  • (2) Définition récursive
    • Soient g: \mathbb{N}^k \rightarrow \mathbb{N} et h : \mathbb{N}^{k+2} \rightarrow \mathbb{N}
    • On dit que f : \mathbb{N}^{k+1}\rightarrow \mathbb{N} est définie récursivement à partir de g et h ssi :
      • f\left(n_1 ,\ldots , n_k, 0\right)=g\left(n_1 ,\ldots , n_k\right)
      • f\left(n_1 ,\ldots , n_k, m+1\right)=h\left(n_1 ,\ldots , n_k, m, f\left(n_1 ,\ldots , n_k, m\right)\right)
    • On notera f=DR(g,h)

• f(n) = succ(succ(n))
• f = succ \circ succ = succ^{(2)}

• plus : \mathbb{N}^2 \rightarrow \mathbb{N}
  • \left(n,m\right) \mapsto n+m
  • plus(n,0) = n
  • plus(n,m+1)=succ(plus(n,m))
  • plus = DR(g,h)
    • g: n\mapsto n, g=id_{1,1}
    • h: \left(n,m,k\right) \mapsto succ\left(id_{3,3}\left(n,m,k\right)\right) = succ\left(k\right)
  • idée : succ\left(plus\left(n,m\right)\right) \rightarrow succ\left(id_{3,3}\left(n,m,plust\left(n,m\right)\right)\right)
• multiplication
  • mult\left(n,0\right) = 0 = zero_1 \left(n\right)
  • mult\left(n,m+1\right) = plus\left(n,mult\left(n,m\right)\right)
  • mult = DR\left(zero, , h\right) ¹⁾
• pred : n\mapsto n-1 \text{ si } n\geq 1, 0 \text{ si } n=0
  • pred(0)=0
  • pred(n+1) = n
• “soustraction” noté ~
  • n ~ 0 = 0
  • n ~ (m+1) = pred(n ~ m)
• puissance : n\uparrow m = n^m : exercice

Fonctions logiques avec “iszero”.

• P : \mathbb{N}^k \rightarrow \left\{0,1\right\}
• iszero(0) = 1
• iszero(m+1) = 0
• \left(n \leq m\right) \; = \; iszero\left(n \sim m\right)
• \left( n \equiv m\right)
  • \left(n \equiv 0\right)=iszero\left(n\right)
  • \left(n \equiv m+1\right)=iszero\left(pred\left(n\right) \sim m\right)
  • iszero\left(n\sim m\right) \text{ et } iszero\left(m\sim n\right)
• \left(non\; n \right)=1 \sim n
• n\text{ et } m = 1 \sim iszero\left(n\cdot m\right)
• n\text{ ou } m = 1 \sim iszero\left(n + m\right)

Ce type de définition convient pour la fonction modulo, le reste de la division euclidienne de m par n, puis pour la division :

• mod(0,n) = 0
• mod(m+1,n) =
  • 0 si pred(n)=mod(m,n)
  • mod(m,n)+1 sinon
• div(0,n) = 0
• div(m+1,n) =
  • div(m,n)+1 si iszero(mod(m+1,n))
  • div(m,n) sinon

L'ensemble des fonctions primitives récursives est dénombrable.

• C'est un ensemble de mots sur l'alphabet \Sigma_{pr} = \left\{zero, id, 0, 1,\circ , \mapsto, DR, (, ), ';'\right\} et \Sigma_{pr}^* est dénombrable.
• Il existe une bijection entre l'ensemble {fonctions primitives récursives} et \mathbb{N}. On sait dénombrer de manière explicite les fonctions primitives récursives.
  • \left(x,k\right) \mapsto f_k\left(x\right) est calculable
  • f_k : k^ième fonction primitive récursive

Il existe des fonctions calculables qui ne sont pas primitives récursives.

• g : m\mapsto f_m\left(m\right) + 1
• g est calculable
• g n'est pas primitive récursive : sinon il existerait k tel que g= f_k et g\left(k\right) = f_k\left(k\right)+1 \neq f_k\left(k\right) .

Définition : Soit g une fonction \mathbb{N}^{k+1} \rightarrow \mathbb{N} . La minimisation de g est la fonction f : \mathbb{N}^k \rightarrow \mathbb{N} définie par

f\left(n_1,\ldots ,n_k\right) = \mu m\left[g\left(n_1,\ldots, n_k, m\right)\right] On n'utilise cette notation que si, quelque soient \left(n_1,\ldots,n_k\right) un tel m existe. Dans ce cas (\forall n_1,\ldots ,n_k\in\mathbb{N}\quad \exists m : g\left(n_1,\ldots n_k,m\right)=1 ) , on dit que la fonction est minimisable.

Savoir si une fonction est minimisable est indécidable.

Définition : les fonctions \mu-récursives sont les fonctions obtenues à partir des fonctions de base (a), (b) et © et les opérations de composition, de définition récursive, et de minimisation pour les fonctions minimisables.

Une fonction f:\mathbb{N}^k \rightarrow \mathbb{N} est \mu -récursive si et seulement si elle est récursive (calculable avec une MT).

voir le cours suivant.

<= cours précédent cours suivant =>