Cours 1 : Introduction, Machines de Turing

comon@lsv.fr

www.lsv.ens-cachan.fr/~comon/

Introduction

Historiquement : qu’est-ce qu’une preuve, avec Hilbert.

  • Gottlob Frege : objectif = formaliser les énoncés et preuves mathématiques (précurseur de la logique du 1er ordre)
  • Bertrand Russell : fait s’effondrer la théorie qu’a développé Frege, avec son paradoxe :
  1. L’ensemble des ensembles qui ne se contiennent pas aux-même n’existe pas : ${x \vert x\not∈ x}$ ⟹ fait éclater la théorie de Frege, car on ne peut pas pearler d’ensemble “qui se contienne”.
  2. Barbier
  3. \(P(Q, D) = \begin{cases} 0 \text{ si } Q(D) = 1 \\ 1 \text{ sinon } \end{cases}\) Si $R(x) ≝ P(x,x)$, alors $R(“R”)=0 ⟺ R(“R”)=1$ ⟶ argument diagonal
    • David Hilbert : “qui nous dit qu’un jour, quelqu’un ne va pas venir détruire tout l’édifice mathématique” ?

Arithmétique élémentaire :

  1. $0 + x = x ∀x$
  2. $succ(x)+y = succ(x+y)$
  3. $0 \times x = 0$
  4. $s(x)\times y = (x\times y)+y$
  5. $s(x) = S(y) ⟹ x=y$
  6. $s(x) \neq 0$
  7. $∀x ∃y x\neq 0 ⟹ x = s(y)$

NB: les formules sont en fait des entiers, dans une base suffisamment grande.

Gödel

  • Cohérence : pour tous $T$, $𝜑$ : $T \not\vdash 𝜑$ OU $T \not\vdash \lnot 𝜑$

  • Complétude : pour tous $T$, $𝜑$ : $T \vdash 𝜑$ OU $T \vdash \lnot 𝜑$

Gödel 1 : Complétude

Si $T$ définit les fonctions récursives et $T$ est cohérent, alors $T$ est incomplet.

⟹ Il y aura toujours des énoncés qui sont indécidables

MAIS : pire : vrai échec du programme Hilbert : c’est le cas de l’arithmétique de Peano, sauf si elle est incohérente.

Dém : A une formule $𝜑$ on associe un entier $<𝜑>$ (une preuve = un arbre de formules où chaque énoncé du père est obtenu par des règles à partir des énoncés des fils).

A une preuve $𝜋$ : idem.

On note $P$ l’ensemble des couples d’entiers $(n,m)$ tels que il existe $𝜑$ à 1 variable libre tq $n = <𝜑>$ et $m = <𝜋(<𝜑(n))>)>$.

⟶ $P$ est récursif : il existe une formule $𝜑_p$ tq \(T \vdash 𝜑_p(n,m) ⟺ (n,m)∈P\)

\[𝜑_D = ∃n; 𝜑_p(n,m)\] \[T \vdash 𝜑_D(<\lnot 𝜑_D>) \\ ⟺ T \vdash ∃n; 𝜑_D(<\lnot 𝜑_D>, n) \\ ⟺ (<\lnot 𝜑_D>, n) \in P \\ ⟺ n \text{ code 1 preuve de $\lnot 𝜑_D(<\lnot 𝜑_D>$)} \\ ⟺ T \vdash \lnot 𝜑_D(<\lnot 𝜑_D>)\]

Programme de Hilbert ⟶ Church ($𝜆$-calcul) ⟶ Thèse de Church : tous les modèles de calcul sont équivalents au $𝜆$-calcul.

Fonctions calculables (ou non)

Problèmes indécidables

  1. Machines de Turing
  2. Exemples de problèmes indécidables : ‡ a) Données : $M_1, ⋯, M_n$ des matrices d’ordre 3 à coefficient dans $ℤ$.

Question : Existe-t-il $k$ tel que : \(∃ i_1, ⋯, i_k; M_{i_1}, ⋯, M_{i_k} = 0\)

b) Donnée : $(u_1, ⋯, u_n), (v_1, ⋯, v_n)$ des uplets de mots.

Question : Existe-t-il $k$ tel que : \(∃ i_1, ⋯, i_k; u_{i_1} ⋯ u_{i_k} = v_{i_1} ⋯ v_{i_k}\)

c) Pavage du quart de plan : Donnée : 1 nb fini de types de tuiles (et une infinité pour un type donné).

Question : est-ce qu’on peut paver le 1/4 du plan en respectant la répétition des motifs ? (cf. dessin)

d) 10e pb de Hilbert : Donnée : $P ∈ ℤ[X_1, ⋯, X_n]$

Question : est-ce qu’il existe un $n$-uplet racine de $P$ ? (indécidable)

e) Fonctions récursive.

Machines de Turing

Déf (cf. dessin) : Un ruban infini, muni d’une tête de lecture et d’états. (B : blanc)

  • $𝛴$ = alphabet fini (on peut montrer qu’on peut se ramener à un alphabet à deux éléments)
    • $$, B ∈ 𝛴$ (première case du ruban : $)
  • $Q$ = ensemble fini d’états
    • $q_0 ∈ Q$ état initial
  • $𝛿 : Q \times 𝛴 ⟶ Q \times 𝛴 \times {⟵, \downarrow, ⟶} ∪ {accept, reject}$

tq : \(∀q, 𝛿(q,\$) ∈ Q\times \{\$\} \times \{\downarrow, ⟶\}\)

Configuration : $(q, w, x)$ où $q ∈ Q, w∈𝛴^, x∈𝛴^$

Mouvement : $(q, w, x) \underbrace{\vdash}_{M} (q’, w’, x’)$

$a$ = première lettre de $x$ ou $B$

$f : 𝛴\backslash{$,B}^* ⟶ 𝛴\backslash{$,B}^$ est calculable s’il existe une machine de turing qui calcule $f$. $M$ calcule $f$ si pour tout $w$, le calcul de $M$ sur $w$ s’arrête dans une configuration $(q, $ w_1, w_2 B^)$ tq $f(w) = w_1 w_2$

$f: ℕ^k ⟶ ℕ$ est calculable si $f^# : {0,1, #}^* ⟶ {0,1}^*$

tq $f^#(\bar{n_1}# ⋯ # \bar{n_k}) = \bar{f(n_1 ⋯ n_k)}$

est calculable.

$L ⊆ {0,1}^*$

$L$ est récursif (décidable) si ∃ une mt tq $L(M)=L$ ET $M$ s’arrête sur tout $w$

$L$ est récursivement énumérable si ∃ une mt tq $L(M)=L$.

Leave a comment