From 4e97c27fce39b69af4f4e192393d51b0bff6847e Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 21 Jan 2025 19:58:30 +0100 Subject: Start writing test for 2025-01-29. --- controle-20250129.tex | 245 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 245 insertions(+) create mode 100644 controle-20250129.tex (limited to 'controle-20250129.tex') 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} -- cgit v1.2.3