Scholarlink

<p>We prove that there exists a partial order having no computable copies in which any effectively interpreted linearly ordered structure has a computable copy, but there are linearly ordered structures with the same degree spectrum which are obtained by a natural algorithmic transformation not directly related to effective interpretability.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Algorithmic Transformations of Partial Orders into Linearly Ordered Structures

  • 期刊论文

  • 发表日期：

    2025年7月1日

查看全文
  • I. Sh. Kalimullin

摘要

We prove that there exists a partial order having no computable copies in which any effectively interpreted linearly ordered structure has a computable copy, but there are linearly ordered structures with the same degree spectrum which are obtained by a natural algorithmic transformation not directly related to effective interpretability.