Complex tilings

被引：25

作者：

Durand, Bruno ^{[1
]}

Levin, Leonid A. ^{[2
]}

Shen, Alexander ^{[3
]}

机构：

[1] Lab Informat Fondamentale Marseille, F-13453 Marseille, France

[2] Boston Univ, Dept Comp Sci, Boston, MA 02215 USA

[3] Inst Problems Informat Transmission, Moscow, Russia

来源：

JOURNAL OF SYMBOLIC LOGIC | 2008年 / 73卷 / 02期

基金：

俄罗斯基础研究基金会; 美国国家科学基金会;

关键词：

tilings; Kolmogorov complexity; recursion theory;

D O I：

10.2178/jsl/1208359062

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with G(n) Kolmogorov complexity of its (n x n)-squares. We construct tile sets for which this bound is tight: all (n x n)-squares in all tilings have complexity Omega(n). This adds a quantitative angle to classical results on non-recursivity of tilings - that we also develop in terms of Turing degrees of unsolvability.

引用

页码：593 / 613

页数：21

共 20 条

[1]

Berger R., 1966, MEMOIRS AM MATH SOC, V66

[2]

Borger E., 1996, CLASSICAL DECISION P

[3]

CERVELLE J, 2000, LECT NOTES COMPUTER, V1770

[4] Local rules and global order, or aperiodic tilings [J].

Durand, B ;

Levin, L ;

Shen, A .

MATHEMATICAL INTELLIGENCER, 2005, 27 (01) :64-68

[5] Tilings and quasiperiodicity [J].

Durand, B .

THEORETICAL COMPUTER SCIENCE, 1999, 221 (1-2) :61-75

[6]

DURAND B, 2001, STOC, P732

[7] Reliable cellular automata with self-organization [J].

Gács, P .

JOURNAL OF STATISTICAL PHYSICS, 2001, 103 (1-2) :45-267

[8] AVERAGE CASE COMPLETENESS [J].

GUREVICH, Y .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 42 (03) :346-398

[9] NONRECURSIVE TILINGS OF PLANE .1. [J].

HANF, W .

JOURNAL OF SYMBOLIC LOGIC, 1974, 39 (02) :283-285

[10]

INGERSENT K, 1991, QUASICRYSTALS STATE, P185

← 1 2 →