We introduce a modification to the Post Correspondence Problem where (in the formulation using morphisms) we require the images to be conjugate words. This problem is then shown to be undecidable by reducing it to the word problem for a special type of semi-Thue systems.


翻译:我们引入了对后通信问题的修正,(在使用形态的配方中)我们要求图像是同义单词。 这个问题通过将它降为一种特殊类型的半硫系统的单词问题来证明是不可分的。

0
下载
关闭预览

相关内容

强化学习最新教程,17页pdf
专知会员服务
182+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
197+阅读 · 2019年10月10日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Arxiv
0+阅读 · 2022年1月10日
VIP会员
相关资讯
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Top
微信扫码咨询专知VIP会员