Undecidability of translational tiling problems
（平移密铺问题的不可判定性）
杨超 副教授
报告时间：2024年12月17日 14:30-17:30
报告地点：北二 立德楼 501室
摘要：Recently, Greenfeld and Tao disproved the conjecture that translational tilings of a single tile can always be periodic [Ann. Math. 200(2024), 301-363]. In another paper [to appear in J. Eur. Math. Soc.], they also show that if the dimension n is part of the input, the translational tiling for subsets of Z^n with one tile is undecidable. These two results are solid evidence for the conjecture that translational tiling of Z^n with a monotile is undecidable, for some fixed n. In general, we study the decidability or undecidability of the following problem: let k and n be fixed positive integers, and a tile is a finite subset of Z^n, given a set S of k tiles in Z^n, is there an algorithm to decide whether Z^n can be tiled by translated copies of tiles in the set S? In this talk, we report some recent progress on the undecidability of this problem based on the joint work with Zhujun Zhang.
报告人简介：杨超，广东外语外贸大学数学与统计学院，副教授，硕士生导师，数学教育系主任。广东省运筹学会理事。本科和博士（硕博连读）均毕业于中国科学技术大学。曾任中山大学数学学院教师，美国德克萨斯州立大学数学系博士后研究员，广东外语外贸大学教务部副部长，广东外语外贸大学应用数学系主任。主持完成国家自然科学基金项目两项，在国内外学术期刊发表学术论文30余篇。主要研究领域为离散几何中的密铺问题，图论与组合博弈论的计算复杂性等。