path: root/controle-20250129.tex

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