%% 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}