Start writing test for 2025-01-29.

1 files changed, 245 insertions, 0 deletions

diff --git a/controle-20250129.tex b/controle-20250129.tex
new file mode 100644
index 0000000..b268a5f
--- /dev/null
+++ b/controle-20250129.tex
@@ -0,0 +1,245 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,hmargin=2cm,vmargin=3cm]{geometry}
+\usepackage[french]{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{mathpartir}
+\usepackage{flagderiv}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\medskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice[1][Exercice]{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{#1~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\dbllangle}{\mathopen{\langle\!\langle}}
+\newcommand{\dblrangle}{\mathclose{\rangle\!\rangle}}
+\newcommand{\dottedlimp}{\mathbin{\dot\Rightarrow}}
+\newcommand{\dottedland}{\mathbin{\dot\land}}
+\newcommand{\dottedlor}{\mathbin{\dot\lor}}
+\newcommand{\dottedtop}{\mathord{\dot\top}}
+\newcommand{\dottedbot}{\mathord{\dot\bot}}
+\newcommand{\dottedneg}{\mathop{\dot\neg}}
+\mathchardef\emdash="07C\relax
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+%
+\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\par\smallbreak\else\egroup\par\fi}
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF110 / CSC-3TC34-TP\\Contrôle de connaissances — Corrigé\\{\normalsize Logique et Fondements de l'Informatique}}
+\else
+\title{INF110 / CSC-3TC34-TP\\Contrôle de connaissances\\{\normalsize Logique et Fondements de l'Informatique}}
+\fi
+\author{}
+\date{29 janvier 2025}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+\textcolor{red}{À revoir.}
+
+Les exercices et le problème sont totalement indépendants.  Ils
+pourront être traités dans un ordre quelconque, mais on demande de
+faire apparaître de façon très visible dans les copies où commence
+chaque exercice (tirez au moins un trait sur toute la largeur de la
+feuille entre deux exercices).
+
+Les questions du problème dépendent les unes des autres, mais ont été
+rédigées de manière à ce que chacune donne toutes les informations
+nécessaires pour passer à la suite.  Mais comme elles (les questions
+du problème) présentent une gradation approximative de difficulté, il
+est recommandé de les traiter dans l'ordre.
+
+La longueur du sujet ne doit pas effrayer : l'énoncé du problème est
+très long parce que des rappels ont été faits et que les questions ont
+été rédigées de façon aussi précise que possible.  Par ailleurs, il ne
+sera pas nécessaire de tout traiter pour avoir le maximum des points.
+
+\medbreak
+
+L'usage de tous les documents écrits (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 3h
+
+Barème \emph{approximatif} et \emph{indicatif} (sur $20$) :
+\textcolor{red}{à écrire}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{à compléter} pages (page de garde incluse).
+\else
+Cet énoncé comporte \textcolor{red}{à compléter} pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\bigbreak
+
+\exercice[Problème]
+
+\textbf{Notations :} Dans cet exercice, on notera comme d'habitude
+$\varphi_e\colon\mathbb{N}\dasharrow\mathbb{N}$ la $e$-ième fonction
+générale récursive (i.e., calculable) pour $e\in\mathbb{N}$.  On
+notera
+\[
+\mathsf{PartCalc} := \{\varphi_e \; : \; e\in\mathbb{N}\}
+= \{g\colon\mathbb{N}\dasharrow\mathbb{N} \; : \;
+\exists e\in\mathbb{N}.\,(g = \varphi_e)\}
+\]
+l'ensemble des fonctions \emph{partielles} calculables
+$\mathbb{N}\dasharrow\mathbb{N}$, ainsi que
+\[
+\mathsf{TotIdx} := \{e\in\mathbb{N} \; : \;
+\varphi_e\hbox{~est totale}\}
+= \{e\in\mathbb{N} \; : \; \varphi_e\in\mathsf{TotCalc}\}
+\]
+l'ensemble des codes des programmes qui définissent une fonction
+\emph{totale} $\mathbb{N}\to\mathbb{N}$ (i.e., terminent et renvoient
+un entier quel que soit l'entier qu'on leur fournit en entrée), et
+\[
+\mathsf{TotCalc} := \{\varphi_e \; : \; e\in\mathsf{TotIdx}\}
+= \{g\colon\mathbb{N}\to\mathbb{N} \; : \;
+\exists e\in\mathbb{N}.\,(g = \varphi_e)\}
+\]
+l'ensemble des fonctions \emph{totales} calculables
+$\mathbb{N}\to\mathbb{N}$, i.e., celles calculées par les programmes
+qu'on vient de dire.
+
+\smallskip
+
+On va s'intéresser à la notion (qu'on va définir) de fonction
+calculable $\mathsf{PartCalc} \to \mathbb{N}$ d'une part, et
+$\mathsf{TotCalc} \to \mathbb{N}$ d'autre part.  (On parle parfois de
+« fonctionnelles » ou de « fonction de second ordre » pour ces
+fonctions sur les fonctions.)  On souligne qu'on parle bien de
+fonction \emph{totales} $\mathsf{PartCalc} \to \mathbb{N}$ d'une part,
+et $\mathsf{TotCalc} \to \mathbb{N}$ d'autre part.
+
+\medskip
+
+\textbf{Définition :} (A) Une fonction (totale !) $F\colon
+\mathsf{PartCalc} \to \mathbb{N}$ est dite \emph{calculable} lorsqu'il
+existe une fonction calculable $\hat F\colon \mathbb{N} \to
+\mathbb{N}$ telle que $\hat F(e) = F(\varphi_e)$ pour tout $e \in
+\mathbb{N}$.\quad (B) De même, une fonction (totale) $F\colon
+\mathsf{TotCalc} \to \mathbb{N}$ est dite calculable lorsqu'il existe
+une fonction calculable $\hat F\colon \mathsf{TotIdx} \to \mathbb{N}$
+telle que $\hat F(e) = F(\varphi_e)$ pour tout $e \in
+\mathsf{TotIdx}$.
+
+\smallskip
+
+En français : une fonctionnelle définie sur l'ensemble des fonctions
+calculables partielles ou partielles est elle-même dite calculable
+lorsqu'il existe un programme qui calcule $F(g)$ à partir du code $e$
+d'un programme calculant $g$.
+
+{\footnotesize
+
+Il est évident que la fonction $\hat F$ vérifie forcément
+$(\varphi_{e_1} = \varphi_{e_2}) \; \Longrightarrow (\hat F(e_1) =
+\hat F(e_2))$ ; c'est-à-dire qu'elle est « extensionnelle » : elle
+doit renvoyer la même valeur sur deux programmes qui calculent la même
+fonction (= ont la même « extension »).  D'ailleurs (on ne demande pas
+de justifier ce fait, qui est facile), se donner une fonction $F\colon
+\mathsf{PartCalc} \to \mathbb{N}$ revient exactement à se donner une
+fonction $\hat F\colon \mathbb{N} \to \mathbb{N}$ ayant cette
+propriété d'« extensionnalité » ; et de même, se donner une fonction
+$F\colon \mathsf{TotCalc} \to \mathbb{N}$ revient exactement à se
+donner une fonction $\hat F\colon \mathsf{TotIdx} \to \mathbb{N}$ qui
+soit extensionnelle.  La définition ci-dessus dit donc que $F$ est
+calculable losrque la $\hat F$ qui lui correspond est elle-même
+calculable.
+
+\par}
+
+\medskip
+
+\textbf{(1)} Montrer que toute fonction (totale !) calculable $F\colon
+\mathsf{PartCalc} \to \mathbb{N}$ est en fait constante.
+
+Pour cela, on pourra supposer par l'absurde que $F$ prend deux valeurs
+distinctes, disons $v_1$ et $v_2$, et considérer l'ensemble des $e$
+tels que $F(\varphi_e) = v_1$ (i.e., $\hat F(e) = v_1$).  (Pourquoi
+est-il décidable ?  Et pourquoi est-ce une contradiction ?)
+
+\medskip
+
+\textbf{(2)} Expliquer pourquoi il existe des fonctions calculables
+(totales) $F\colon \mathsf{TotCalc} \to \mathbb{N}$ qui ne sont pas
+constantes.
+
+Pour cela, on pourra penser évaluer en un point, c'est-à-dire
+exécuter, le programme qu'on a reçu en argument (on rappellera
+pourquoi on peut faire cela).
+
+\medskip
+
+Fixons maintenant une fonction calculable $F\colon \mathsf{TotCalc}
+\to \mathbb{N}$.  On cherche à démontrer qu'elle a la propriété
+suivante (« théorème de Kreisel-Lacombe-Shoenfield ») : quelle que
+soit $g \in \mathsf{TotCalc}$, il existe $n_0$ telle que pour toute
+fonction $g' \in \mathsf{TotCalc}$ qui coïncide avec $g$ jusqu'au rang
+$n_0$ (i.e. : $\forall i\leq n_0.\,(g'(i) = g(i))$) on ait $F(g') =
+F(g)$.
+
+
+
+%
+%
+%
+\end{document}