ucl-ingi / lingi1123-calculabilite Goto Github PK

Donner des exemples pour illustrer les concepts section 2.1

Donner des exemples de MT. Et un exemple d'une exécution.

Ajouter démonstration des propriétés

• Tout sous-ensemble d’un ensemble énumérable est énumérable.
• L’union et l’intersection de deux ensembles énumérables sont énumérables.

La démonstration de Rice par le point fixe ne donne pas ne version plus forte de Rice. C'est le même théorème, mais prouvé autrement.

La Remarque dans le théorème n'est pas claire. Je ne comprends pas exactement ce que cela dit...

Replacer les paragraphes introductifs du chapitre dans une nouvelle section "Qu'est-ce que la calculabilité".
Etendre cette section avec des exemples de limites dans d'autres domaines scientifiques

Donner et expliquer les propriétés des fonctions primitves récursives (cfr slides)

Corriger les imprécisions de la preuve.

Donner des exemples d'automates finis

Donner un exemple des différentes définitions : dérivation, arbres syntaxiques.

Transférer les exemples d'ensembles non énumérable de la section 2.2 à la fin de la section 2.3.

Donner des exemples d'ensemble énumérable (cfr slides), et montrer pourquoi ils sont énumérables.

Paragraphe introductif à compléter.
La sous-section résultats principaux doit devenir une section à par entière (cfr autre Issue)

Comme introducxtion au théorème de Rice, donner les exemples des slides. Pour chaque exemple, montrer comment démontrer la non récursivité de l’ensemble par une réduction à HALT.

A la fin de la section 3, ajouter une sous-section "Au delà du non énumérable". Existe-t-il des ensemble qui ont plus d'éléments que R ? Oui. Donner des exemples.

Réécrire la preuve du théorème Il existe une fonction partielle calculable g telle qu’aucune fonction totale calculable n’est une extension de g.

La preuve du théorème de Rice contient pas mal d'imprécisions... A corriger

Donner des exemples de fonctions primitives récursives (cfr slides).

Compléter la description de la non calculabilité de la détection de virus.

• Définir nuisible
• Préciser ce qu'on veut faire: démontrer que la fonction detecteur(P,D) ne peut pas être réalisée par un programme qui ne soit pas lui-même nuisible.
• Expliquer que preuve par contradiction. Supposons qu'il existe un programme detecteur(P,D) qui ne soit pas nuisible. Alors il existe un programme pour drole(P). ...

Ecrire un énoncé complet du théorème de Hoare-Allison

Décrire dans la section "Résultats fondamentaux" ce qu'est un problème intrinsèquement complexe. Donner un exemple.

Ajouytre des exemples et applications du théorème de Rice.

Donner un exemple simple de grammaire (constante réelle en Java).

Démontrer les propriétés "ND-récursif ssi récursif" et "ND-récursivement énumnérable ssi récursivement énumérable". Bonne idée de d'abord démontrer la propriété précédente sur la simulation d'un programme ND par un programme D. Faire cette preuve et parler de complexité exponentiel de cette simulation

inclure schéma des problèmes calculables / non calculables + explications
Décrire l'intérêt de la calculabilité et de la complexité.

La démonstration existant ne proue qu'un seul sens du SSi. Il reste à prouver l'autre sens.

Expliquer à quoi sert ce théorème. Central en calculabilité car il est le point de départ de tous les résultats (avec la propriété S).

Réécrire l'introduction plus clairement.

Expliquer et justifier pourquoi les différentes extensions ont la même puissance. Expliquer intuitivement comment on peut simuler le modèle avec une MT standard (ou vice versa si modèle plus "élémentaire").

Ajouter une section Résultats Principaux, avec 3 sous-sections. (1) Equivalence des langages de programmation. (2) Existence de problèmes non calculables. (3) Existence de problèmes intrinsèquement complexes.
Intégrer la section existante Détection de virus dans la nouvelle sous-section "Existence de problèmes non calculables"

Exemple 8 (ensemble des chaînes infinies de caractères sur un alphabet fini): donner un exemple concret. Utiliser cet exemple pour montrer que l'ensemble défini par le produit cartésien d'une infinité énumérable d'ensembles énumérables (voir même finis) n'est pas énumérable; contrairement à l'union d'une infinité énumérable d'ensembles énumérables.

Montrer comment on peut représenter un entier en Lambda calcul, et comment on peut réaliser des opérations de base sur ces entiers (cfr slides).

Dans le package de style lingi1123.sty, il y a au début du fichier une importation du package eplcode.sty alors que le contenu de celui-ci est déjà recopié dans lingi1123.sty (ligne 95 à 125) rendant son importation inutile. Ne vaudrait-il donc pas mieux supprimer eplcode.sty ? (Bien que cela n'ait pas beaucoup d'impact sur la compilation cela rendrait le code plus lisible)

Donner des exemples d'expressions lambda et de réduction