From 06043c0f14dc6ddb1be75ff1247834cd23cb64f7 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 23 Jan 2017 17:15:53 +0100 Subject: Move notes on computability to main text. --- notes-calculabilite.tex | 605 ------------------------------------------------ notes-inf105.tex | 573 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 573 insertions(+), 605 deletions(-) delete mode 100644 notes-calculabilite.tex diff --git a/notes-calculabilite.tex b/notes-calculabilite.tex deleted file mode 100644 index 835acea..0000000 --- a/notes-calculabilite.tex +++ /dev/null @@ -1,605 +0,0 @@ -\documentclass[12pt,a4paper]{article} % -*- coding: utf-8 -*- -\usepackage[a4paper]{geometry} -\usepackage[francais]{babel} -\usepackage[utf8]{inputenc} -\usepackage[T1]{fontenc} -\usepackage{times} -\usepackage{amsmath} -\usepackage{amsfonts} -\usepackage{amssymb} -\usepackage{amsthm} -\usepackage{mathrsfs} -%\usepackage{bm} -\usepackage{stmaryrd} -\usepackage{wasysym} -\usepackage{url} -\usepackage{graphicx} -\usepackage[usenames,dvipsnames]{xcolor} -%\usepackage{tikz} -%\usetikzlibrary{matrix,arrows,decorations.markings} -\usepackage{hyperref} -% -% -% -\theoremstyle{definition} -\newtheorem*{defn}{Définition} -\newtheorem*{prop}{Proposition} -\newtheorem*{lem}{Lemme} -\newtheorem*{thm}{Théorème} -\newtheorem*{cor}{Corollaire} -\renewcommand{\qedsymbol}{\smiley} -% -\mathchardef\emdash="07C\relax -\mathchardef\hyphen="02D\relax -\DeclareUnicodeCharacter{00A0}{~} -% -% -% -\begin{document} -\pretolerance=8000 -\tolerance=50000 - -\textbf{Discussion préalable.} On s'intéresse ici à la question de -savoir ce qu'un \textbf{algorithme} peut ou ne peut pas faire. Pour -procéder de façon rigoureuse, il faudrait formaliser la notion -d'algorithme (par exemple à travers le concept de machine de Turing) : -on a préféré rester informel sur cette définition — par exemple « un - algorithme est une série d'instruction précises indiquant des - calculs à effectuer étape par étape et qui ne manipulent, à tout - moment, que des données finies » ou « un algorithme est quelque - chose qu'on pourrait, en principe, implémenter sur un ordinateur » — -étant entendu que cette notion est déjà bien connue et comprise, au -moins dans la pratique. Les démonstrations du fait que tel ou tel -problème est décidable par un algorithme ou que telle ou telle -fonction est calculable par un algorithme deviennent beaucoup moins -lisibles quand on les formalise avec une définition rigoureuse -d'algorithme (notamment, programmer une machine de Turing est encore -plus fastidieux que programmer en assembleur un ordinateur, donc -s'il s'agit d'exhiber un algorithme, c'est probablement une mauvaise -idée de l'écrire sous forme de machine de Turing). - -Néanmoins, il est essentiel de savoir que ces formalisations -existent : on peut par exemple évoquer le paradigme du -$\lambda$-calcul de Church (la première formalisation rigoureuse de la -calculabilité), les fonctions générales récursives (=$\mu$-récursives) -à la Herbrand-Gödel-Kleene, les machines de Turing (des machines à -états finis capables de lire, d'écrire et de se déplacer sur un ruban -infini contenant des symboles d'un alphabet fini dont à chaque instant -tous sauf un nombre fini sont des blancs), les machines à registres, -le langage « FlooP » de Hofstadter, etc. Toutes ces formalisations -sont équivalentes (au sens où, par exemple, elles conduisent à la même -notion de fonction calculable ou calculable partielle, définie -ci-dessous). La \textbf{thèse de Church-Turing} affirme, au moins -informellement, que tout ce qui est effectivement calculable par un -algorithme\footnote{Voire, dans certaines variantes, physiquement - calculable dans notre Univers.} est calculable par n'importe -laquelle de ces notions formelles d'algorithmes, qu'on peut rassembler -sous le nom commun de \textbf{calculabilité au sens de Church-Turing}, -ou « calculabilité » tout court. - -Notamment, quasiment tous les langages de programmation -informatique\footnote{C, C++, Java, Python, JavaScript, Lisp, OCaml, - Haskell, Prolog, etc. Certains langages se sont même révélés - Turing-complets alors que ce n'était peut-être pas voulu : par - exemple, HTML+CSS.}, au moins si on ignore les limites des -implémentations et qu'on les suppose capables de manipuler des -entiers, chaînes de caractère, tableaux, etc., de taille arbitraire -(mais toujours finie)\footnote{Autre condition : ne pas utiliser de - générateur aléatoire matériel.}, sont « Turing-complets », -c'est-à-dire équivalents dans leur pouvoir de calcul à la -calculabilité de Church-Turing. Pour imaginer intuitivement la -calculabilité, on peut donc choisir le langage qu'on préfère et -imaginer qu'on programme dedans. Essentiellement, pour qu'un langage -soit Turing-complet, il lui suffit d'être capable de manipuler des -entiers de taille arbitraire, de les comparer et de calculer les -opérations arithmétiques dessus, et d'effectuer des tests et des -boucles. - -\medbreak - -Il faut souligner qu'on s'intéresse uniquement à la question de savoir -ce qu'un algorithme peut ou ne peut pas faire (calculabilité), pas au -temps ou aux autres ressources qu'il peut prendre pour le faire -(complexité), et on ne cherche donc pas à rendre les algorithmes -efficaces en quelque sens que ce soit. Par exemple, pour arguër qu'il -existe un algorithme qui décide si un entier naturel $n$ est premier -ou non, il suffit de dire qu'on peut calculer tous les produits $pq$ -avec $2\leq p,q\leq n-1$ et tester si l'un d'eux est égal à $n$, peu -importe que cet algorithme soit absurdement inefficace. De même, nos -algorithmes sont capables de manipuler des entiers arbitrairement -grands : ceci permet de dire, par exemple, que toute chaîne binaire -peut être considérée comme un entier, peu importe le fait que cet -entier ait peut-être des milliards de chiffres (dans les langages -informatiques réels, on a rarement envie de considérer toute donnée -comme un entier, mais en calculabilité on peut se permettre de le -faire). - -Notamment, plutôt que de considérer des « mots » (éléments -de $\Sigma^*$ avec $\Sigma$ un alphabet fini) et « langages » (parties -de $\Sigma^*$), il sera plus pratique de remplacer l'ensemble -$\Sigma^*$ des mots par l'ensemble des entiers naturels, quitte à -choisir un codage (calculable !) des mots par des entiers. (À titre -d'exemple, on obtient une bijection de l'ensemble $\{0,1\}^*$ des mots -sur l'alphabet à deux lettres avec $\mathbb{N}$ de la façon suivante : -ajouter un $1$ au début du mot, lire celui-ci comme un nombre binaire, -et soustraire $1$. Plus généralement, une fois choisi un ordre total -sur l'alphabet fini $\Sigma$, on peut trier les mots par ordre de -taille, et, à taille donnée, par ordre lexicographique, et leur -associer les entiers naturels dans le même ordre : il n'est pas -difficile de montrer que cela donne bien une bijection calculable -entre $\Sigma^*$ et $\mathbb{N}$.) - -\medbreak - -\textbf{Terminaison des algorithmes.} Un algorithme qui effectue un -calcul utile doit certainement terminer en temps fini. Néanmoins, -même si on voudrait ne s'intéresser qu'à ceux-ci, il n'est pas -possible d'ignorer le « problème » des algorithmes qui ne terminent -jamais (et ne fournissent donc aucun résultat). C'est le point -central de la calculabilité (et du théorème de Turing ci-dessous) -qu'on ne peut pas se débarrasser des algorithmes qui ne terminent -pas : on ne peut pas, par exemple, formaliser une notion -suffisante\footnote{Tout dépend, évidemment, de ce qu'on appelle - « suffisant » : il existe bien des notions de calculabilité, plus - faibles que celle de Church-Turing, où tout calcul termine, voir par - exemple la notion de fonction « primitive récursive » ou le langage - « BlooP » de Hofstadter ; mais de telles notions ne peuvent pas - disposer d'une machine universelle comme expliqué plus loin (en - raison d'un argument diagonal), donc elles sont nécessairement - incomplètes en un certain sens.} de calculabilité dans laquelle tout -algorithme termine toujours ; ni développer un langage de -programmation suffisamment général dans lequel il est impossible qu'un -programme « plante » indéfiniment ou parte en boucle infinie. (Cette -subtilité est d'ailleurs sans doute en partie responsable de la -difficulté historique à dégager la bonne notion d'« algorithme » : on -a commencé par développer des notions d'algorithmes terminant -forcément, comme les fonctions primitives récursives, et on se rendait -bien compte que ces notions étaient forcément toujours incomplètes.) - -\bigbreak - -\begin{defn} -On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est -\textbf{calculable} (ou « récursive ») lorsqu'il existe un algorithme -qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, -et calcule (renvoie) $f(n)$. - -On dit qu'un ensemble $A \subseteq \mathbb{N}$ (« langage ») est -\textbf{décidable} (ou « calculable » ou « récursif ») lorsque sa -fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ -(valant $1$ sur $A$ et $0$ sur son complémentaire) est calculable. -Autrement dit : lorsqu'il existe un algorithme qui prend en entrée -$n\in\mathbb{N}$, termine toujours en temps fini, et renvoie -« oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que -l'algorithme « décide » $A$). - -On dit qu'une fonction partielle -$f\colon\mathbb{N}\dasharrow\mathbb{N}$ (c'est-à-dire une fonction -définie sur une partie de $\mathbb{N}$, appelé ensemble de définition -de $f$) est \textbf{calculable partielle} (ou « récursive partielle ») -lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, -termine en temps fini ssi $f(n)$ est définie, et dans ce cas calcule -(renvoie) $f(n)$. (Une fonction calculable est donc simplement une -fonction calculable partielle qui est toujours définie : on dira -parfois « calculable totale » pour souligner ce fait.) - -On dit qu'un ensemble $A \subseteq \mathbb{N}$ est -\textbf{semi-décidable} (ou « semi-calculable » ou « semi-récursif ») -lorsque la fonction partielle $\mathbb{N}\dasharrow\mathbb{N}$ définie -exactement sur $A$ et y valant $1$, est calculable partielle. -Autrement dit : lorsqu'il existe un algorithme qui prend en entrée -$n\in\mathbb{N}$, termine en temps fini ssi $n \in A$, et renvoie -« oui » ($1$) dans ce cas\footnote{En fait, la valeur renvoyée n'a pas - d'importance ; on peut aussi définir un ensemble semi-décidable - comme l'ensemble de définition d'une fonction calculable partielle.} -(on dira que l'algorithme « semi-décide » $A$). -\end{defn} - -On s'est limité ici à des fonctions d'une seule variable (entière), -mais il n'y a pas de difficulté à étendre ces notions à plusieurs -variables, et de parler de fonction calculable $\mathbb{N}^k \to -\mathbb{N}$ (voire $\mathbb{N}^* \to \mathbb{N}$ avec $\mathbb{N}^*$ -l'ensemble des suites finies d'entiers naturels) ou de fonction -calculable partielle de même type : de toute manière, on peut « coder » -un couple d'entiers naturels comme un seul entier naturel (par exemple -par $(m,n) \mapsto 2^m(2n+1)$, qui définit une bijection calculable -$\mathbb{N}^2 \to \mathbb{N}$), ou bien sûr un nombre fini quelconque -(même variable), ce qui permet de faire « comme si » on avait toujours -affaire à un seul paramètre entier. - -{\footnotesize \textbf{Complément :} Comme on n'a pas défini - formellement la notion d'algorithme, il peut être utile de signaler - explicitement les faits suivants (qui devraient être évidents sur - toute notion raisonnable d'algorithme) : les fonctions constantes - sont calculables ; les opérations arithmétiques usuelles sont - calculables ; les projections $(n_1,\ldots,n_k) \mapsto n_i$ sont - calculables, ainsi que la fonction qui à $(m,n,p,q)$ associe $p$ si - $m=n$ et $q$ sinon ; toute composée de fonctions calculables - (partielle ou totale) est calculable idem ; si $\underline{m} - \mapsto g(\underline{m})$ est calculable (partielle ou totale) et - que $(\underline{m}, n, v) \mapsto h(\underline{m}, n, v)$ l'est, - alors la fonction $f$ définie par récurrence par $f(\underline{m},0) - = g(\underline{m})$ et $f(\underline{m},n+1) = h(\underline{m}, n, - f(\underline{m},n))$ est encore calculable idem (algorithmiquement, - il s'agit juste de boucler $n$ fois) ; et enfin, si $(\underline{m}, - n) \mapsto g(\underline{m},n)$ est calculable partielle, alors la - fonction $f$ (aussi notée $\mu_n g$) définie par $f(\underline{m}) = - \min\{n : g(\underline{m},n) = 0 \land \forall n'