왕 타일

왕 타일(Wang tile) 또는 왕 도미노(Wang dominoes)는 수학자, 논리학자, 철학자 왕 하오가 1961년에 처음 제안한 형식 체계의 한 종류이다. 각 면에 색이 있는 정사각형 타일로 시각적으로 모델링된다. 이러한 타일 세트가 선택되고, 타일 복사본은 회전하거나 반사하지 않고 일치하는 색상으로 나란히 배열된다.

왕 타일 세트에 대한 기본적인 질문은 평면을 타일링할 수 있는지 여부, 즉 전체 무한 평면을 이런 방식으로 채울 수 있는지 여부이다. 다음 질문은 이것이 주기적인 패턴으로 수행될 수 있는지 여부이다.

도미노 문제
섬네일|400px|13개의 타일로 왕 테셀레이션을 한 예시.
1961년, 왕은 유한한 왕 타일 세트가 평면을 타일링할 수 있다면, 주기적 타일링도 존재할 것이라고 추측했다. 주기적 타일링은 수학적으로 2차원 격자의 벡터에 의한 변환에 불변인 타일링이다. 이는 전체 패턴이 더 작은 패턴의 반복인 벽지 패턴의 주기적 타일링과 유사할 수 있다. 그는 또한 이 추측이 주어진 유한한 왕 타일 세트가 평면을 타일링할 수 있는지 여부를 결정하는 알고리즘의 존재를 의미할 것이라고 관찰했다.. Wang proposes his tiles and conjectures that there are no aperiodic sets.. Presents the domino problem for a popular audience. 인접한 타일이 서로 일치하도록 제한하는 아이디어는 도미노 게임에서 발생하므로 왕 타일은 왕 도미노라고도 알려져 있다.. 타일 세트가 평면을 타일링할 수 있는지 여부를 결정하는 알고리즘 문제는 도미노 문제로 알려지게 되었다.

왕의 학생인 로버트 버거에 따르면,
도미노 문제는 모든 도미노 세트의 클래스를 다룬다. 각 도미노 세트에 대해 풀 수 있는지 여부를 결정하는 것으로 구성된다. 우리는 임의의 도미노 세트의 사양이 주어졌을 때, 그 세트가 풀 수 있는지 여부를 결정하는 알고리즘이 존재하거나 존재하지 않는지에 따라 도미노 문제가 결정 가능하거나 결정 불가능하다고 말한다.
즉, 도미노 문제는 주어진 모든 도미노 세트에 대해 문제를 올바르게 해결하는 효과적인 절차가 있는지 묻는 것이다.

1966년, 버거는 도미노 문제를 부정적으로 해결했다. 그는 튜링 기계가 멈추지 않는 경우에만 평면을 타일링하는 왕 타일 세트로 모든 튜링 기계를 번역하는 방법을 보여줌으로써 문제에 대한 알고리즘이 존재할 수 없음을 증명했다. 정지 문제 (튜링 기계가 결국 멈추는지 여부를 테스트하는 문제)의 결정 불가능성은 왕의 타일링 문제의 결정 불가능성을 의미한다..  Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.

비주기적 타일 세트
섬네일|각 사분면의 가장자리를 해당 색상에 해당하는 모양으로 대체하여 단색으로 만든 왕 타일 – 이 세트는 위에 있는 Jeandel과 Rao의 최소 세트와 동형이다.
버거의 결정 불가능성 결과와 왕의 관찰을 결합하면 평면을 타일링하지만 비주기적으로만 타일링하는 유한한 왕 타일 세트가 존재해야 한다는 것을 보여준다. 이것은 펜로즈 테셀레이션이나 준결정의 원자 배열과 유사하다. 버거의 원래 세트에는 20,426개의 타일이 포함되어 있었지만, 그는 그의 세트의 하위 세트를 포함하여 더 작은 세트가 작동할 것이라고 추측했으며, 그의 미출판 박사 학위 논문에서 타일 수를 104개로 줄였다. 이후 몇 년 동안 점점 더 작은 세트가 발견되었다... (Showed an aperiodic set of 13 tiles with 5 colors.).. (Showed an aperiodic set of 11 tiles with 4 colors, and proved that fewer tiles or fewer colors cannot be aperiodic.) 예를 들어, 13개의 비주기적 타일 세트는 1996년 카렐 쿨릭 2세에 의해 발표되었다.

가장 작은 비주기적 타일 세트는 2015년 에마뉘엘 장델과 미카엘 라오에 의해 11개의 타일과 4개의 색상으로 발견되었다. 그들은 10개의 타일이나 3개의 색상으로는 비주기성을 강제하기에 불충분하다는 것을 증명하기 위해 철저한 컴퓨터 탐색을 사용했다. 제목 이미지에 표시된 이 세트는 :파일: Wang 11 tiles.svg에서 더 자세히 볼 수 있다.

일반화
왕 타일은 다양한 방식으로 일반화될 수 있으며, 이 모든 것은 위에서 언급한 의미에서 결정 불가능하다. 예를 들어, 왕 큐브는 색상이 있는 면을 가진 동일한 크기의 큐브이며, 면 색상은 어떤 다각형 테셀레이션에서도 일치시킬 수 있다.
쿨릭과 카리는 왕 큐브의 비주기적 세트를 시연했다.. 윈프리 외는 왕 타일 역할을 할 수 있는 DNA (디옥시리보핵산)로 만들어진 분자 "타일"을 만드는 가능성을 시연했다.. 미탈 외는 이러한 타일이 펩타이드 핵산 (PNA), 즉 안정적인 인공 DNA 모방체로도 구성될 수 있음을 보여주었다..

응용
왕 타일은 절차적 합성으로 절차적 텍스처, 높이 필드 및 기타 크고 비반복적인 2차원 데이터 세트를 생성하는 데 사용되었다. 미리 계산되거나 수작업으로 만든 작은 소스 타일 세트는 너무 명백한 반복과 주기성 없이 매우 저렴하게 조립될 수 있다.
이 경우 전통적인 비주기적 테셀레이션은 매우 규칙적인 구조를 보여줄 것이다. 타일링 가능성이 쉽게 보장되고 각 타일을 유사 무작위로 선택할 수 있으므로 주어진 두 면 색상에 대해 최소한 두 가지 타일 선택을 보장하는 훨씬 덜 제약적인 세트가 일반적이다.. Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.. Introduces stochastic tiling... Applies Wang Tiles for real-time texturing on a GPU.. . Shows advanced applications.

왕 타일은 세포 자동자 이론의 결정 문제 결정 가능성 증명에도 사용되었다..

대중 문화에서
그레그 이건의 단편 소설 "왕의 카펫"은 나중에 소설 디아스포라로 확장되었는데, 복합 분자 패턴으로 구현된 왕 타일로 구현된 거주 생물과 지능 있는 존재가 있는 우주를 가정한다..

 같이 보기 
 가장자리 일치 퍼즐

 각주 

더 읽어보기
 .

 외부 링크 
 스티븐 더치의 비주기적 테셀레이션 그림 페이지
 단순한 왕 타일링 방법의 애니메이션 시연 - Javascript 및 HTML5 필요

분류:계산 이론
분류:1961년 도입
분류:유클리드 평면 테셀레이션
분류:비주기적 테셀레이션