-
Notifications
You must be signed in to change notification settings - Fork 3
/
913.tex
137 lines (106 loc) · 5.34 KB
/
913.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
\documentclass{agregfiche}
\title{Leçon 913 -- Machines de Turings. Applications.}
% V1 par Emilie Grienberger
% Relu par Aliaume Lopez, Charlie Jacomme
% Relu par Jean Goubaut-Larrecq
\begin{document}
\maketitle
\secrapports
\begin{rapport}{2019}
Il s'agit de présenter un modèle de calcul.
Le candidat doit expliquer l'intérêt de disposer d'un modèle formel de calcul et discuter le choix des machines de Turing.
La leçon ne peut se réduire à la leçon 914 ou à la leçon 915, même si, bien sûr, la complexité et l'indécidabilité sont des exemples d'applications.
Plusieurs développements peuvent être communs avec une des leçons 914, 915, mais il est apprécié qu'un développement spécifique soit proposé.
\end{rapport}
\begin{rapport}{2018}
[idem]
+ [\dots] soit proposé, comme le lien avec d'autres modèles de calcul, ou le lien entre diverses variantes des machines de Turing.
\end{rapport}
\secindispensables
\begin{itemize}
\item Définitions des machines de \bsc{Turing} déterministes.
\item Reconnaissabilité (mot, langage). Codages de langages. % l'un des intérêt du modèle est de pouvoir coder beaucoup de choses.
\item Machine de \bsc{Turing} universelle.
\item Définition d'un problème décidable, indécidable. Problème de l'arrêt.
\end{itemize}
\secasavoir
\begin{itemize}
\item Stabilité des notions pour les variantes des machines de \bsc{Turing} : non
déterminisme (existentiel, universel, alternant),
plusieurs rubans, alphabet ou nombre d'états restreints. % encore un intérêt du modèle.
\item Machine non déterministes.
\item Langages récursifs, récursivement énumérables.
\item Indécidabilité, \bsc{Rice} et réductions.
\item Calculabilité : définition d'une fonction calculable.
\item Exemples de fonctions calculables : fonctions arithmétiques.
\item Expressivité : équivalence avec les fonctions récursives.
\item Complexité : définition de la complexité en temps, espace.
\end{itemize}
\secidees
\begin{itemize}
\item Ne pas oublier des exemples, pour montrer comment fonctionne le modèle.
\item Équivalence avec le lambda-calcul.
\item Limites de la stabilité (machines en espace linéaire/constant,
machines n'écrivant pas sur leur entrée,
calculant en temps $o(\log \log n)$).
\item Lien avec des notions plus faibles de calcul (automates, grammaires
algébriques).
\item Lien avec les machines à compteur (de \bsc{Minsky}), ou les machines RAMs.
\item Des classes au delà du récursivement énumérable. (si on sait justifier leur intérêt) % $\pi_1$ complet implique qu'on est non capturable par la logique
\end{itemize}
\secpieges
\begin{itemize}
\item Beaucoup de choses à dire, pas besoin de partir dans des choses pas maîtrisées.
\item Cf rapport, ne pas avoir une leçon trop inspirée des leçons 914, 915.
\item Chaque livre a une définition des machines de Turing : il faut rester cohérent, et faire attention aux résultats utilisés.
\item MOTIVER ! Justifier le formalisme introduit et son utilité en comparaison
aux autres modèles.
\item Une machine de \bsc{Turing} peut calculer une fonction, reconnaître un langage, ou bien l'énumérer. Comprendre les différences et les liens entre ces notions.
\item Faire attention à la reconnaissabilité pour les machines
non déterministes.
\item Attention aux définitions de bases sur la reconnaissabilité, où des petits changements de définition peuvent fortement changer ce qu'on obtient. Notamment sur les notions d'arrêt sur toute entrées.
\item Attention à bien travailler sur des $Q$ et $\Sigma$
finis.
\item Il est facile d'illustrer le principe du ruban et de la tête de lecture par un dessin.
\end{itemize}
\secquestionsclassiques
\begin{itemize}
\item Quel est l'intérêt des machines de Turing ?
% c'est une abstraction bas niveau de ce qu'on peut calculer avec des algorithmes. C'est donc pratique pour raisonner dessus, mais pas fait pour écrire des algorithmes.
\item Quel sens donner au \emph{calcul} d'une machine de Turing non
déterministe ?
\item Pourquoi préférer les machines de \bsc{Turing} aux machines RAM ?
% notion de localité des calculs.
\item Quel est l'intérêt d'une machine de Turing universelle ?
% ordinateur programmable
\item Dans quel sens une machine de Turing est-elle proche d'un ordinateur
classique ?
% un ordinateur = Turing + Ram
\item En quoi les classes de complexités sont liées à l'efficacité des
algorithmes ?
% temps de calcul de TM reliable à celui d'un ordi.
\item Pourquoi étudier principalement la décidabilité plutôt que la
calculabilité ?
% plus agréable de travailler sur des langages plutot que des
%nombres.
\end{itemize}
\secreferences
\begin{itemize}
\item \input{refs/carton}
\item \input{refs/wolper}
\item \input{refs/sipser}
\item \input{refs/arorabarak}
% \item Éviter le \bsc{papadimitriou}, souvent faux dans ses preuves.
\end{itemize}
\secdev
\begin{itemize}
\item[+] \input{dev/turingismurecusrive}
\item[-] \input{dev/cook}
\item[+] \input{dev/arretTM}
\item[++] \input{dev/equivdefTM}
\end{itemize}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: