diff options
Diffstat (limited to 'transp-inf110-01-calc.tex')
| -rw-r--r-- | transp-inf110-01-calc.tex | 97 |
1 files changed, 52 insertions, 45 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 2970367..649fd14 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -1,7 +1,13 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\newif\ifbeamermode +\beamermodetrue +\ifbeamermode \documentclass[mathserif,a4paper,aspectratio=169]{beamer} -%\documentclass[a4paper]{article} -%\usepackage{beamerarticle} +\else +\documentclass[a4paper]{article} +\usepackage{beamerarticle} +\usepackage[a4paper,margin=2.5cm]{geometry} +\fi \usepackage[shorthands=off,french]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} @@ -38,19 +44,20 @@ \newcommand{\myitemmark}{\hbox{$\blacktriangleright$}} \renewcommand{\itempoint}{\strut\myitemmark\nobreak\hskip.5em plus.5em\relax} \setlength{\parindent}{0pt} + \renewcommand{\thepage}{I–\arabic{page}} } % % % -\title{Calculabilité} +\title{{\footnotesize Partie I:} Calculabilité} \subtitle{INF110 (Logique et Fondements de l'Informatique)} \author[David Madore]{David A. Madore\\ {\footnotesize Télécom Paris}\\ \texttt{david.madore@enst.fr}} -\date{2023–2024} +\date{2023–2025} \mode<presentation>{% \beamertemplatenavigationsymbolsempty -\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}} +\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize(I) \hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}} } \setbeamercolor{myhighlight}{fg=black,bg=white!90!green} \begin{document} @@ -909,8 +916,8 @@ Pseudocode : \smallskip {\footnotesize\texttt{% -str="somefunc(code) \{ /*...*/ \}\textbackslash nsomefunc(\textbackslash"str=\textbackslash"+quote(str)+str);\textbackslash n";\\ -somefunc(code) \{ /*...*/ \}\\ +str="somefunc(code) \{ /*...*/ \}\textbackslash nsomefunc(\textbackslash"str=\textbackslash"+quote(str)+str);\textbackslash n";\newline +somefunc(code) \{ /*...*/ \}\newline somefunc("str="+quote(str)+str); }\par} @@ -1653,14 +1660,14 @@ Pseudocode : \smallskip {\footnotesize\texttt{% -fibonacci(n) \{\\ -str = "self = \textbackslash"fibonacci(n) \{\textbackslash \textbackslash nstr = \textbackslash" + quote(str) + str;\textbackslash n\textbackslash\\ -if (n==0 || n==1) return n;\textbackslash n\textbackslash\\ -return interpret(self, n-1) + interpret(self, n-2);\textbackslash n\textbackslash\\ -\}";\\ -self = "fibonacci(n) \{\textbackslash nstr = " + quote(str) + str;\\ -if (n==0 || n==1) return n;\\ -return interpret(self, n-1) + interpret(self, n-2);\\ +fibonacci(n) \{\newline +str = "self = \textbackslash"fibonacci(n) \{\textbackslash \textbackslash nstr = \textbackslash" + quote(str) + str;\textbackslash n\textbackslash\newline +if (n==0 || n==1) return n;\textbackslash n\textbackslash\newline +return interpret(self, n-1) + interpret(self, n-2);\textbackslash n\textbackslash\newline +\}";\newline +self = "fibonacci(n) \{\textbackslash nstr = " + quote(str) + str;\newline +if (n==0 || n==1) return n;\newline +return interpret(self, n-1) + interpret(self, n-2);\newline \} }\par} @@ -1773,7 +1780,7 @@ Supposons par l'absurde $h$ est calculable : alors cette fonction (partielle) $v$ est calculable, disons $v = \varphi_c$. Si $\varphi_c(c)\downarrow$ alors $h(c,c)=1$ donc $v(c)\uparrow$, -c'est-à-dire $\varphi_c(c)\uparrow$, contradiction.\\ Si +c'est-à-dire $\varphi_c(c)\uparrow$, contradiction.\newline Si $\varphi_c(c)\uparrow$ alors $h(c,c)=0$ donc $v(c)\downarrow$, c'est-à-dire $\varphi_c(c)\downarrow$, contradiction.\qed @@ -3614,13 +3621,13 @@ non-évalué (exemple transp. suivant). \itempoint Récursion sans combinateurs : {\tt -(define proto-fibonacci\\ -\ \ (lambda (self) ; Pass me as argument!\\ -\ \ \ \ (lambda (n)\\ -\ \ \ \ \ \ (if (<= n 1) n\\ -\ \ \ \ \ \ \ \ \ \ (+ ((self self) (- n 1)) ((self self) (- n 2)))))))\\ -(define fibonacci (proto-fibonacci proto-fibonacci))\\ -(map fibonacci '(0 1 2 3 4 5 6))\\ +(define proto-fibonacci\newline +\ \ (lambda (self) ; Pass me as argument!\newline +\ \ \ \ (lambda (n)\newline +\ \ \ \ \ \ (if (<= n 1) n\newline +\ \ \ \ \ \ \ \ \ \ (+ ((self self) (- n 1)) ((self self) (- n 2)))))))\newline +(define fibonacci (proto-fibonacci proto-fibonacci))\newline +(map fibonacci '(0 1 2 3 4 5 6))\newline $\rightarrow$ (0 1 1 2 3 5 8) \par} @@ -3641,19 +3648,19 @@ cette construction. \frametitle{Digression (suite) : exemple en Scheme} {\tt -;; (define y-combinator\\ -;; \ \ (lambda (f)\\ -;; \ \ \ \ ((lambda (x) (f (x x))) (lambda (x) (f (x x))))))\\ -(define z-combinator\\ -\ \ (lambda (f)\\ -\ \ \ \ ((lambda (x) (f (lambda (v) ((x x) v))))\\ -\ \ \ \ \ (lambda (x) (f (lambda (v) ((x x) v)))))))\\ -(define pre-fibonacci\\ -\ \ (lambda (fib)\\ -\ \ \ \ (lambda (n)\\ -\ \ \ \ \ \ (if (<= n 1) n\\ -\ \ \ \ \ \ \ \ \ \ (+ (fib (- n 1)) (fib (- n 2)))))))\\ -(define fibonacci (z-combinator pre-fibonacci))\\ +;; (define y-combinator\newline +;; \ \ (lambda (f)\newline +;; \ \ \ \ ((lambda (x) (f (x x))) (lambda (x) (f (x x))))))\newline +(define z-combinator\newline +\ \ (lambda (f)\newline +\ \ \ \ ((lambda (x) (f (lambda (v) ((x x) v))))\newline +\ \ \ \ \ (lambda (x) (f (lambda (v) ((x x) v)))))))\newline +(define pre-fibonacci\newline +\ \ (lambda (fib)\newline +\ \ \ \ (lambda (n)\newline +\ \ \ \ \ \ (if (<= n 1) n\newline +\ \ \ \ \ \ \ \ \ \ (+ (fib (- n 1)) (fib (- n 2)))))))\newline +(define fibonacci (z-combinator pre-fibonacci))\newline \par} \end{frame} @@ -3860,15 +3867,15 @@ Exemple en OCaml (ici, \texttt{loop} produit une boucle infinie) : \smallskip {\footnotesize -\texttt{type t = T of (t -> t)}\\ -\texttt{let apply : t -> t -> t = fun (T rator) -> fun rand -> rator rand}\\ -\texttt{let id : t = T (fun x -> x)}\hfill\texttt{(* }$\lambda x.x$\texttt{ *)}\\ -\texttt{let ch0 : t = T (fun f -> T (fun x -> x))}\hfill\texttt{(* }$\lambda fx.x$\texttt{ *)}\\ -\texttt{let ch1 : t = T (fun f -> T (fun x -> apply f x))}\hfill\texttt{(* }$\lambda fx.fx$\texttt{ *)}\\ -\texttt{let ch2 : t = T (fun f -> T (fun x -> apply f (apply f x)))}\hfill\texttt{(* }$\lambda fx.f(fx)$\texttt{ *)}\\ -\texttt{let om : t = T (fun x -> apply x x)}\hfill\texttt{(* }$\lambda x.xx$\texttt{ *)}\\ -\texttt{let loop : t = apply om om}\hfill\texttt{(* }$(\lambda x.xx)(\lambda x.xx)$\texttt{ *)}\\ -\texttt{(* let loop = (fun (T h) -> h (T h)) (T (fun (T h) -> h (T h))) *)}\\ +\texttt{type t = T of (t -> t)}\newline +\texttt{let apply : t -> t -> t = fun (T rator) -> fun rand -> rator rand}\newline +\texttt{let id : t = T (fun x -> x)}\hfill\texttt{(* }$\lambda x.x$\texttt{ *)}\newline +\texttt{let ch0 : t = T (fun f -> T (fun x -> x))}\hfill\texttt{(* }$\lambda fx.x$\texttt{ *)}\newline +\texttt{let ch1 : t = T (fun f -> T (fun x -> apply f x))}\hfill\texttt{(* }$\lambda fx.fx$\texttt{ *)}\newline +\texttt{let ch2 : t = T (fun f -> T (fun x -> apply f (apply f x)))}\hfill\texttt{(* }$\lambda fx.f(fx)$\texttt{ *)}\newline +\texttt{let om : t = T (fun x -> apply x x)}\hfill\texttt{(* }$\lambda x.xx$\texttt{ *)}\newline +\texttt{let loop : t = apply om om}\hfill\texttt{(* }$(\lambda x.xx)(\lambda x.xx)$\texttt{ *)}\newline +\texttt{(* let loop = (fun (T h) -> h (T h)) (T (fun (T h) -> h (T h))) *)}\newline \par} \medskip |