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

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.