We study the algorithmic undecidability of abstract dynamical properties for sofic $\mathbb{Z}^{2}$-subshifts and subshifts of finite type (SFTs) on $\mathbb{Z}^{2}$. Within the class of sofic $\mathbb{Z}^{2}$-subshifts, we prove the undecidability of every nontrivial dynamical property. We show that although this is not the case for $\mathbb{Z}^{2}$-SFTs, it is still possible to establish the undecidability of a large class of dynamical properties. This result is analogous to the Adian-Rabin undecidability theorem for group properties. Besides dynamical properties, we consider dynamical invariants of $\mathbb{Z}^{2}$-SFTs taking values in partially ordered sets. It is well known that the topological entropy of a $\mathbb{Z}^{2}$-SFT can not be effectively computed from an SFT presentation. We prove a generalization of this result to \emph{every} dynamical invariant which is nonincreasing by factor maps, and satisfies a mild additional technical condition. Our results are also valid for $\Z^{d}$, $d\geq2$, and more generally for any group where determining whether a subshift of finite type is empty is undecidable.


翻译:暂无翻译

0
下载
关闭预览

相关内容

Group一直是研究计算机支持的合作工作、人机交互、计算机支持的协作学习和社会技术研究的主要场所。该会议将社会科学、计算机科学、工程、设计、价值观以及其他与小组工作相关的多个不同主题的工作结合起来,并进行了广泛的概念化。官网链接:https://group.acm.org/conferences/group20/
牛津大学最新《计算代数拓扑》笔记书,107页pdf
专知会员服务
42+阅读 · 2022年2月17日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
可解释AI(XAI)工具集—DrWhy
专知
25+阅读 · 2019年6月4日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
概率图模型体系:HMM、MEMM、CRF
机器学习研究会
30+阅读 · 2018年2月10日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
基于LDA的主题模型实践(三)
机器学习深度学习实战原创交流
23+阅读 · 2015年10月12日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关VIP内容
牛津大学最新《计算代数拓扑》笔记书,107页pdf
专知会员服务
42+阅读 · 2022年2月17日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
可解释AI(XAI)工具集—DrWhy
专知
25+阅读 · 2019年6月4日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
概率图模型体系:HMM、MEMM、CRF
机器学习研究会
30+阅读 · 2018年2月10日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
基于LDA的主题模型实践(三)
机器学习深度学习实战原创交流
23+阅读 · 2015年10月12日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员