왕타일

Wang tile
이 11개의 왕 타일 세트는 비행기의 타일을 만들지만 주기적으로만 타일을 만들 것이다.

1961년 수학자·논리학자·철학자 하오왕이 처음 제안한 왕타일(또는 왕도미노)은 형식 시스템의 일종이다. 그것들은 양쪽에 색상이 있는 사각 타일로 시각적으로 모델링된다. 이러한 타일 세트를 선택하고, 타일 사본은 회전하거나 반영하지 않고 서로 다른 색상으로 나란히 배열한다.

왕 타일 세트에 대한 기본적인 질문은 비행기에 타일을 칠할 수 있느냐, 즉 무한 평면 전체를 이렇게 채울 수 있느냐 하는 것이다. 다음 질문은 이것이 주기적인 패턴으로 이루어질 수 있는가 하는 것이다.

도미노 문제

13개의 타일을 사용한 왕 테셀레이션의 예.

1961년 왕타일 유한 세트가 비행기를 타일링할 수 있다면 주기적인 타일링, 즉 벽지 무늬처럼 2차원 격자 안의 벡터에 의한 번역 아래 불변하는 타일링도 존재한다고 왕 교수는 추측했다. 그는 또한 이러한 추측이 주어진 한정된 왕 타일 세트가 평면에 타일을 칠할 수 있는지를 결정하는 알고리즘의 존재를 암시할 것이라고 관측했다.[1][2] 인접한 기와를 서로 일치시키기 위해 구속한다는 생각이 도미노 게임에서 일어나기 때문에 왕 타일은 왕 도미노라고도 한다.[3] 타일 세트가 비행기를 타일로 묶을 수 있는지 여부를 결정하는 알고리즘적인 문제가 도미노 문제로 알려지게 되었다.[4]

왕 선생의 제자 로버트 버거에 [4]따르면

Domino 문제는 모든 Domino 세트의 클래스를 다룬다. 그것은 각 도미노 세트에 대해 해결 가능한지 여부를 결정하는 것으로 구성된다. 우리는 Domino 문제가 임의의 도미노 세트의 규격에 따라 해결 가능한지 여부를 결정하는 알고리즘이 존재하는지 존재하지 않는지에 따라 결정 가능하거나 결정 불가능하다고 말한다.

즉, 도미노 문제는 주어진 모든 도미노 세트에 대해 문제를 정확하게 해결하는 효과적인 절차가 있는지 묻는다.

1966년 버거는 도미노 문제를 네거티브로 해결했다. 그는 튜링 기계가 정지하지 않을 경우에만 어떤 튜링 기계도 비행기의 타일을 만드는 왕 타일 세트로 변환하는 방법을 보여줌으로써 문제의 알고리즘이 존재할 수 없음을 증명했다. 정지 문제(튜링 기계가 결국 정지하는지를 시험하는 문제)의 불분명한 것은 왕정화의 타일링 문제의 불분명한 것을 내포하고 있다.[4]

Aperiodic tails sets

왕 타일은 각 사분면의 가장자리를 색깔에 상응하는 모양으로 교체하여 단색화를 만들었다. 이 세트는 제안델과 라오의 최소 세트와 같은 형태다.

버거의 불운한 결과와 왕씨의 관찰 결과를 종합하면, 비행기에 타일을 다는 왕 타일들의 유한한 집합이 존재해야 하지만, 주기적으로만 존재한다는 것을 알 수 있다. 이것은 펜로즈 타일링 또는 퀘이시크리스탈의 원자의 배열과 유사하다. 버거의 원래 세트에는 2만426개의 타일이 들어 있었지만, 자신의 세트 서브셋을 포함해 더 작은 세트가 통할 것으로 추측했고, 미발표 박사 논문에서는 104개로 타일을 줄였다. 나중에, 점점 더 작은 세트들이 발견되었다.[5][6][7][8] 예를 들어, 13개의 주기적 타일 세트는 1996년에 카렐 쿨릭 2세에 의해 출판되었다.[6]

2015년 에마뉘엘 잔델과 마이클 라오가 발견한 가장 작은 주기적 타일 세트는 11개의 타일, 4개의 색이다. 그들은 10개의 타일이나 3개의 색이 주기성을 강요하기에 불충분하다는 것을 증명하기 위해 철저한 컴퓨터 검색을 이용했다.[8] 제목 영상에 나타난 이 세트는 File(파일)에서 보다 면밀하게 검토할 수 있다.왕11 타일.svg.

일반화

왕 타일은 여러 가지 방법으로 일반화할 수 있는데, 이 모든 것은 위의 의미에서도 이해할 수 없는 것이다. 예를 들어, 왕 큐브는 같은 크기의 정육면체로서 색상이 있는 얼굴이며, 어떤 다각형 테셀레이션에서도 사이드 컬러를 매치할 수 있다. 컬릭과 카리는 왕 큐브의 주기적인 세트를 보여주었다.[9] 윈프리 외 왕 타일 역할을 할 수 있는 디옥시리보핵산(Deoxyrivonucleic acid)으로 만든 분자 "타일"을 만들 수 있는 가능성을 입증했다.[10] 미탈 외 이 타일들은 DNA의 안정적인 인공 모방인 펩타이드 핵산(PNA)으로도 구성될 수 있다는 것을 보여주었다.[11]

적용들

왕 타일은 최근 텍스처, 높이장 및 기타 크고 반복되지 않는 비복원적 데이터 세트의 절차적 합성을 위한 인기 있는 도구가 되었다.; 미리 계산된 또는 수작업으로 만들어진 작은 소스 타일 세트는 너무 명백한 반복과 주기성 없이 매우 저렴하게 조립할 수 있다. 이 경우 전통적인 주기적 기울기는 매우 규칙적인 구조를 보일 수 있다. 타일성을 쉽게 보장하고 각 타일을 유사하게 선택할 수 있기 때문에 주어진 두 가지 측면 색상에 대해 적어도 두 가지 타일 선택을 보장하는 훨씬 덜 제약적인 세트가 일반적이다.[12][13][14][15][16]

왕 타일은 세포 자동이론 검증에도 사용되었다.[17]

대중문화에서

그렉 이간의 단편 왕 카펫은 나중에 소설 디아스포라로 확대되어, 복잡한 분자의 패턴에 의해 구현된 왕 타일로 구현된, 상주하는 유기체와 지적인 존재들로 완성된 우주를 상정한다.[18]

참고 항목

참조

  1. ^ 왕씨는 그의 타일을 제안하고, 주기적인 세트가 없다고 추측한다Wang, Hao (1961), "Proving theorems by pattern recognition—II", Bell System Technical Journal, 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x.
  2. ^ 인기 있는 청중을 위해 도미노 문제를 제시한다Wang, Hao (November 1965), "Games, logic and computers", Scientific American, 213 (5): 98–106, doi:10.1038/scientificamerican1165-98.
  3. ^ Renz, Peter (1981), "Mathematical proof: What it is and what it ought to be", The Two-Year College Mathematics Journal, 12 (2): 83–103, doi:10.2307/3027370, JSTOR 3027370.
  4. ^ a b c 버거는 "왕 타일"이라는 용어에 동전을 붙이고, 그것들의 첫 번째 주기적인 세트를 보여준다Berger, Robert (1966), "The undecidability of the domino problem", Memoirs of the American Mathematical Society, 66: 72, MR 0216954.
  5. ^ Robinson, Raphael M. (1971), "Undecidability and nonperiodicity for tilings of the plane", Inventiones Mathematicae, 12 (3): 177–209, Bibcode:1971InMat..12..177R, doi:10.1007/bf01418780, MR 0297572.
  6. ^ a b Culik, Karel, II (1996), "An aperiodic set of 13 Wang tiles", Discrete Mathematics, 160 (1–3): 245–251, doi:10.1016/S0012-365X(96)00118-5, MR 1417576. (5색 타일 13개로 구성된 주기적 세트 표시).
  7. ^ Kari, Jarkko (1996), "A small aperiodic set of Wang tiles", Discrete Mathematics, 160 (1–3): 259–264, doi:10.1016/0012-365X(95)00120-L, MR 1417578.
  8. ^ a b Jeandel, Emmanuel; Rao, Michael (2021), "An aperiodic set of 11 Wang tiles", CoRR, arXiv:1506.06492, Bibcode:2015arXiv150606492J, doi:10.19086/aic.18614. (4색 타일 11개로 구성된 주기적 세트 표시)}
  9. ^ Culik, Karel, II; Kari, Jarkko (1995), "An aperiodic set of Wang cubes", Journal of Universal Computer Science, 1 (10): 675–686, doi:10.1007/978-3-642-80350-5_57, MR 1392428.
  10. ^ Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C. (1998), "Design and self-assembly of two-dimensional DNA crystals", Nature, 394 (6693): 539–544, Bibcode:1998Natur.394..539W, doi:10.1038/28998, PMID 9707114.
  11. ^ Lukeman, P.; Seeman, N.; Mittal, A. (2002), "Hybrid PNA/DNA nanosystems", 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii.
  12. ^ Stam, Jos (1997), Aperiodic Texture Mapping (PDF). 결정론적 대체 시스템과 함께 질감 변화에 왕 타일을 사용하는 아이디어를 소개한다.
  13. ^ 확률적인 타일링을 도입한다Neyret, Fabrice; Cani, Marie-Paule (1999), "Pattern-Based Texturing Revisited", Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH '99 (PDF), Los Angeles, United States: ACM, pp. 235–242, doi:10.1145/311535.311561, ISBN 0201485605.
  14. ^ Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), "Wang tiles for image and texture generation", ACM SIGGRAPH 2003 Papers on - SIGGRAPH '03 (PDF), New York, NY, USA: ACM, pp. 287–294, doi:10.1145/1201775.882265, ISBN 1-58113-709-5, archived from the original (PDF) on 2006-03-18.
  15. ^ Wei, Li-Yi (2004), "Tile-based texture mapping on graphics hardware", Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM, pp. 55–63, doi:10.1145/1058129.1058138, ISBN 3-905673-15-0. GPU에 실시간 텍스처링에 왕타일 적용.
  16. ^ . 고급 응용 프로그램 표시
  17. ^ Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena, vol. 45, pp. 379–385, Bibcode:1990PhyD...45..379K, doi:10.1016/0167-2789(90)90195-U, MR 1094882.
  18. ^ Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN 9780252096297.

추가 읽기

외부 링크