论文标题
可计算性通过遗传二阶逻辑
Computability by Monadic Second-Order Logic
论文作者
论文摘要
当图形上的二进制关系在且仅当它可以通过单层二阶逻辑中的公式计算时，才能递归枚举。后者意味着该公式以通常的方式定义了一组图，以便该集合中的每个“计算图”都确定由输入图和输出图组成的对。
A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula in monadic second-order logic. The latter means that the formula defines a set of graphs, in the usual way, such that each "computation graph" in that set determines a pair consisting of an input graph and an output graph.
