From ac8bffe7083b4f2a2d3e4a8c66297c1c46da1bf0 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 30 Jan 2017 14:42:17 +0100 Subject: Clarify statement on busy-beaver function. --- exercices3.tex | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'exercices3.tex') diff --git a/exercices3.tex b/exercices3.tex index 8d5c0ad..c8bee33 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -708,14 +708,15 @@ connaissance de $M$ permet de résoudre le problème de l'arrêt. Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq M(k)$ pour tout $k$ n'est calculable. Montrer que même si $M'$ vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est -pas calculable. Bref, la fonction $M$ croît plus vite que n'importe -quelle fonction calculable. +pas calculable. \emph{Remarque :} La fonction $M$, ou différentes variantes de celle-ci, s'appelle fonction du « castor affairé ». On peut montrer -encore plus fort : si $M'(k)\geq M(k)$ pour un nombre infini de -valeurs de $k$, alors $M'$ n'est pas calculable (Radó, 1962, -\textit{On Non-Computable Functions}). +encore plus fort : si $F$ est une fonction calculable quelconque, +alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$ +(autrement dit, la fonction $M$ finit par dépasser n'importe quelle +fonction calculable : Radó, 1962, \textit{On Non-Computable + Functions}). \begin{corrige} Supposons que $M$ soit calculable. On peut alors résoudre le problème -- cgit v1.2.3