#grammar-hierarchy

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Luis M. Augusto

本文从形式语言理论的角度重新审视 Emil Post 提出的“生产性集合”(productive set) 概念,并据此构造出本质上不可判定的形式文法。背景上,Post 证明存在这样一类自然数集合:它们不是递归可枚举的,甚至连半可计算都做不到——不存在任何图灵机能在有限步内枚举其全部元素,其补集可被递归枚举而集合自身不可枚举,这类集合即生产性集合;若进一步满足更强条件则称为“完全生产性”。由此可推出,任何以生产性集合作为其词集的形式语言都不可能是递归可枚举的,也就是无法被图灵机半判定,属于“本质不可判定”的语言,其地位比乔姆斯基体系中最宽的第 0 型递归可枚举语言还要“超出图灵阈值”。论文的核心方法是:把 Post 关于自然数生产性集合的经典构造(通过不断产生“新元素”,使任何候选枚举器都无法封闭其输出集合)翻译到文法规则设计中,从而显式构造出一族能够生成生产性词集的形式文法,并论证这些文法所定义的语言既不可计算也非递归可枚举。作者明确指出这是一项构造性、概念性的理论工作,而非实验性研究:其贡献在于把可计算性理论中关于不可判定性的经典边界结果系统地带入形式文法与语言层级的语境,给出“超越图灵可判定性”的文法形式刻画,并提示语言层级中存在位于递归可枚举语言之上的层次。适合可计算性理论、形式语言与自动机理论的研究者阅读,也适合关心程序分析、形式验证与静态分析工具判定边界的工程读者。

💡 推荐理由: 它从文法层面给出“哪些语言根本无法被算法判定”的形式证据,有助于安全工程师认清静态分析、形式验证、符号执行等工具的能力上限:某些程序性质不是工具不够强,而是原则上不可半判定,继续堆检测规则或追求“完备检测”并不现实。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.4)