Beyond the Turing threshold: Productive grammars generate essentially undecidable languages

本文从形式语言理论的角度重新审视 Emil Post 提出的“生产性集合”(productive set) 概念，并据此构造出本质上不可判定的形式文法。背景上，Post 证明存在这样一类自然数集合：它们不是递归可枚举的，甚至连半可计算都做不

历史摘要 · 未重新核验 · arXiv cs.CR