Problema de correspondencia de Post
Post correspondence problem
- Fecha
- 1946 · fiabilidad alta
- Lugar
- Nueva York, Nueva York, Estados Unidos
- Autoría
- Emil Leon Post
- Ámbito
- Saber y símbolos
Qué se descubrió
Emil Post formuló un problema de decisión sobre listas de fichas de dominó con palabras que resultó ser indecidible, más sencillo de plantear que el problema de la parada.
A qué dio paso
- Demostraciones de indecidibilidad en lógica
- Prueba de que ciertas gramáticas son ambiguas
- Enseñanza de la teoría de la computabilidad
- Aplicaciones en teoría de lenguajes formales