Write a sample exercice on computability.

1 files changed, 197 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
new file mode 100644
index 0000000..eb19a9f
--- /dev/null
+++ b/exercices3.tex
@@ -0,0 +1,197 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage[hyperindex=false]{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\relax\else\egroup\fi\par}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{Exercices divers — Corrigé}
+\else
+\title{Exercices divers}
+\fi
+\author{David A. Madore}
+\maketitle
+
+\centerline{\textbf{INF105}}
+
+{\footnotesize
+\immediate\write18{sh ./vc > vcline.tex}
+\begin{center}
+Git: \input{vcline.tex}
+\end{center}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pretolerance=8000
+\tolerance=50000
+
+
+
+%
+%
+%
+
+\exercice
+
+On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est
+dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un
+programme pour une machine de Turing) prenant en entrée un
+$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la
+valeur $f(n)$.  On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de
+$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction
+indicatrice est calculable, ou, ce qui revient au même, lorsqu'il
+existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou
+de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
+vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non
+à $E$.  On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de
+$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un
+algorithme prenant en entrée un élément de $\mathbb{N}$ ou de
+$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
+vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine
+pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne
+change rien).
+
+Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a
+équivalence entre les affirmations suivantes :
+\begin{enumerate}
+\item la fonction $f$ est calculable,
+\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} =
+  \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable,
+\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
+\end{enumerate}
+
+(Montrer que (3) implique (1) est le plus difficile : on pourra
+commencer par s'entraîner en montrant que (2) implique (1).  Pour
+montrer que (3) implique (2), on pourra chercher une façon de tester
+en parallèle un nombre croissant de valeurs de $p$ de manière à
+s'arrêter si l'une quelconque convient.)
+
+\begin{corrige}
+Montrons que (1) implique (2) : si on dispose d'un algorithme capable
+de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un
+algorithme capable de décider si $p=f(n)$ (il suffit de calculer
+$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur
+de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et
+faux/$0$ sinon).
+
+Le fait que (2) implique (3) est évident car tout ensemble décidable
+est semi-décidable.
+
+Montrons que (2) implique (1) même si ce ne sera au final pas utile :
+supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e.,
+donnés $(n,p)$, termine toujours en temps fini, en répondant oui si
+$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme
+qui calcule $f(n)$.  Pour cela, donné un $n$, il suffit de lancer
+l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$
+puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie
+sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un
+$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la
+valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition
+de $T$.
+
+Reste à montrer que (3) implique (1) : supposons qu'on ait un
+algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$,
+termine en temps fini et répond oui si $p=f(n)$, et ne termine pas
+sinon), et on cherche à écrire un algorithme qui calcule $f(n)$.  Pour
+cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes
+et faire tendre $M$ vers l'infini : plus exactement, on utilise
+l'algorithme $U$ suivant :
+\begin{itemize}
+\item pour $M$ allant de $0$ à l'infini,
+\begin{itemize}
+\item pour $p$ allant de $0$ à $M$,
+\begin{itemize}
+\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au
+  plus $M$ étapes,
+\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$
+  (sinon, continuer les boucles).
+\end{itemize}
+\end{itemize}
+\end{itemize}
+
+(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de
+valeurs de $p$ de plus en plus grand et en attendant de plus en plus
+longtemps pour voir si l'une d'elles termine.)
+
+Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément
+$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$,
+et on renvoie la valeur en question) ; il reste à expliquer pourquoi
+$U$ termine toujours.  Mais la valeur $f(n)$ existe (même si on ne la
+connaît pas) car la fonction $f$ était supposée définie partout, et
+lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé
+terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur
+à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être
+prise par $p$ dans la boucle intérieure, et pour cette valeur,
+l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$
+étapes, ce qui assure que $U$ termine effectivement.
+
+L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
+prouve (1).
+\end{corrige}
+
+
+%
+%
+%
+\end{document}