Comments on Notes de cours de théorie des langages formels

Ruxor (2017-11-23T18:08:33Z)

@Xavier Combelle: Oui, les services informatiques de Télécom ont cassé des choses en migrant mon compte d'un disque à un autre. Je ne sais pas comment ils ont fait leur compte (le fichier est pourtant bien disponible sur le serveur) ni quand ça sera réparé. En attendant, j'ai mis une copie du document dans <URL: http://www.madore.org/~david/.tmp/notes-inf105.pdf >.

Xavier Combelle (2017-11-23T14:39:02Z)

404 not found on https://perso.telecom-paristech.fr/~madore/inf105/notes-inf105.pdf

Ruxor (2017-11-17T14:40:53Z)

@JMU: Non, je compile avec l'option -shell-escape de pdflatex et je m'en sers pour invoquer un script trivial qui écrit le numéro de version dans un fichier .tex que j'inclus ensuite. Voir lignes 83‒91 de <URL: http://git.madore.org/cgit/teach/inf105.git/tree/notes-inf105.tex?id=f1826f0f50ca2ff35761222b64d6312ac87bbc77 >, ainsi que le script lui-même <URL: http://git.madore.org/cgit/teach/inf105.git/tree/vc?id=f1826f0f50ca2ff35761222b64d6312ac87bbc77 >.

JMU (2017-11-17T12:30:33Z)

Rien à voir, mais ma curiosité est titillée à la vue de la référence du commit dans le fichier compilé. Tu as mis un post-commit hook qui édite le .tex ?

xavier (2017-11-11T18:09:44Z)

ok merci pour la clarification :)

Ruxor (2017-11-11T13:44:10Z)

@xavier: Il y a un résultat théorique, pour lequel je n'ai d'ailleurs aucune référence, qui dit que si une fonction est calculable avec probabilité 1 par une machine de Turing disposant d'un générateur aléatoire fort (i.e., il y a un programme T, faisant appel à un oracle, qui, quel que soit n, calcule f(n) avec probabilité 1 si l'oracle répond aléatoirement), alors en fait cette fonction est calculable sans générateur aléatoire (i.e., par une machine de Turing ordinaire). Donc au moins en ce sens-là (i.e., si on demande que le même résultat soit calculé avec probabilité 1), le fait d'ajouter un générateur aléatoire n'apporte rien. Mais dans l'autre sens, toute séquence aléatoire *donnée* est, avec probabilité 1, incalculable par une machine de Turing (ça c'est essentiellement trivial comme fait). En l'occurrence, je suppose l'absence de générateur aléatoire pour éviter toute discussion sur la question.

xavier (2017-11-11T13:07:20Z)

Note 25 sur le générateur aléatoire : Hum si on en rajoute un à une machine de Turing on y gagne quoi? Uniquement le fait d'avoir de l'aléatoire "fort" (c'est quoi cette bête) ou on gagne autre chose?

ooten (2017-11-11T12:51:28Z)

Il est super ton cours même si je ne l'ai que très partiellement parcouru. J'ai toujours aimé les long cours théoriques fruit d'un travail parfois multi séculaire dans ma jeunesse. Celui là en aurait certainement fait parti ☺


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: e9ccee


Recent comments