Indécidabilité de la terminaison d'un système de réécriture : Différence entre versions

Version actuelle en date du 31 mars 2015 à 15:21

On montre que le problème de la terminaison d'un système de réécriture est indécidable.

Développement

• Indécidabilité de la terminaison d'un système de réécriture.

Référence

Baader Nipkow, Term rewriting and all that.

Recasements

• 913 -- Machines de Turing. Applications.
• 914 -- Décidabilité et indécidabilité. Exemples.
• 920 -- Réécriture et formes normales. Exemples.
• 922 -- Ensembles récursifs, récursivement énumérables. Exemples.