테렌스 타오(Terence Tao)가 또 다른 60년 기하학 문제에 접근합니다! 주기적인 밀착 포장 문제에 새로운 돌파구가 마련되었습니다.

Tao Zhexuan은 주기 타일링 문제 연구에 새로운 돌파구를 마련했습니다

9월 18일 Tao Zhexuan과 Rachel Greenfeld는 사전 인쇄 논문 "Undecidability of Translational Monotilings"를 arXiv에 업로드했습니다.

문서 주소: https://arxiv.org/abs/2309.09504

이 논문의 주요 결론은 그리드의 차원이 무한하다면 그리드의 유한 분할을 결정한다는 것입니다. 집합이 그리드의 주기적인 부분 집합을 타일링할 수 있는지 여부에 대한 질문은 결정 불가능합니다

이 문제는 차원 1과 차원 2에서 결정 가능합니다.

Tao Zhexuan은 기사에서 시연된 대부분의 구성 요소가 인기 게임과 유사하다는 것이 조금 이상하다고 말했습니다.

도미노의 타일 유사품, 스도쿠, 컴퓨터 게임 "테트리스" " , 어린이용 게임 '피즈 버즈'까지 등장

수학 문제를 공부하는데 왜 이렇게 많은 게임이 필요한 걸까요? Tao Zhexuan 또한 병진 단일 조밀 타일링의 결정불가능성을 설명할 수 없습니다. 이 논문은 두 사람의 이전 논문의 후속편입니다. 링크 주기 타일 문제

마지막 논문에서 그들은 고차원 그리드의 병진 단일 조밀 타일링

을 구성했습니다(그래서 단일 조밀 타일링은 유한 집합), 비주기적입니다(이 타일링을 주기적인 타일링 으로 "수정"할 수 있는 방법이 없습니다. 여기서

은 이제 유한 인덱스 하위 그룹

에 대해 주기적입니다). 이 사실은 비주기적 조밀하게 포장된 단량체가 존재하지 않는다는 Stein, Grunbaum-Shephard 및 Lagarias-Wang의 가설을 부정합니다. ("Hat Single Densely Packed"는 최근 발견된 비주기적 등각 투영 단일체입니다. 회전, 반사 및 이동이 허용되는 촘촘한 타일링

또는 업데이트된 "고스트 모놀리스" 위의 모놀리스는 반사가 필요하지 않다는 점을 제외하면 모자 단일 촘촘한 타일링과 유사합니다.

Tao Zhexuan과 Rachel Greenfeld가 이 추측에 영감을 준 이유 중 하나는 수학자 Hao Wang의 관찰입니다.

그는 주기적 타일링 추측이 참이라면 병진 타일링 문제가 알고리즘적으로 결정 가능하다는 것을 발견했습니다. ——

튜링 기계가 있습니다. 에 대해 차원 과 유한 부분집합 이 주어지면 이 테셀레이션될 수 있는지 가 제한된 시간 내에 결정될 수 있습니다.

주기적인 타일링이 있으면 컴퓨터 검색을 통해 찾을 수 있기 때문입니다.

타일링이 전혀 없으면 압축 정리를 통해 유한한 서브가 있음을 알 수 있습니다. 집합, 이러한 하위 집합은 분리된 번역으로 처리할 수 없으며 컴퓨터 검색으로도 찾을 수 있습니다.

주기적 테셀레이션 추측은 이것이 유일한 두 가지 가능한 상황임을 주장하여 결정 가능성을 제공합니다.

반면에 Wang의 관점은 불변입니다. 주기적 테셀레이션 추측의 실패가 다른 알고리즘의 존재를 배제하지 않기 때문에 자동으로 변환 단일 테셀레이션 문제의 결정 불가능성을 의미하지는 않습니다. 테셀레이션을 결정하면 이 테셀레이션은 주기적인 테셀레이션의 존재와 무관할 수 있습니다

(예를 들어 새로 발견된 모자와 고스트 테셀레이션의 경우에도 에서 유리수 계수를 갖는 다각형의 등각 단순 단면에 대해 열려 있는 상태로 유지됩니다. 조밀한 타일링 문제가 반사 여부에 따라 결정 가능한지 여부에 대한 질문입니다.

이 문서의 주요 결과는 이 문제를 다루고 있습니다(주의 사항 있음). 정리 1 ere에 대한 알고리즘은 없으며,주기적인 서브 세트

및 유한 서브 세트

가 주어지면 내부에 패닝 가 있는지 여부를 결정할 수 있습니다. 제한된 시간

.

모두 보다는 의 주기적 하위 집합 을 사용해야 한다는 점에 유의하는 것이 중요합니다. 이는 주로 이 접근 방식의 기술적 한계로 인한 것이며 추가 노력과 창의성을 통해 달성될 가능성이 높습니다. 제거하기.

또한 Terence Tao와 Rachel Greenfeld도 때 Bhattacharya에 의해 주기적인 포장 추측이 확립되었으므로 이 경우 문제는 결정 가능하다는 사실을 알아차렸습니다 .

의 고정된 값에 대해 타일링 문제가 결정 가능한지 여부는 여전히 열려 있습니다(위 결과에서 차원 은 고정되지 않고 입력의 일부입니다).

알고리즘 결정 불가능성과 논리적 결정 불가능성(논리적 독립성이라고도 함) 사이의 잘 알려진 연결로 인해 이 정리는 (원칙적으로 명확하게 설명할 수 있는) 차원의 존재를 암시합니다. of , 및 의 유한 부분 집합 은 이 번역 타일링 을 통과하도록 하며 ZFC 집합 이론에서 확인되거나 위조될 수 없습니다(물론 이론이 일관성이 있다고 가정). . 이 접근 방식의 결과로 여기에서

를 "거의 2차원" 그룹 으로 대체할 수도 있습니다. 여기서 는 유한 아벨 그룹입니다(이제 입력의 일부, 대신 Dimensions ). 다음으로, 증명의 주요 아이디어 몇 가지를 설명하세요.

문제가 결정 불가능하다는 것을 증명하는 일반적인 방법은 결정 불가능하다고 알려진 다른 문제를 원래 문제로 "인코딩"하여 원래 문제를 결정하는 알고리즘이 내장된 문제도 결정할 수 있도록 하는 것입니다

따라서 우리는 Wang Dense Shop 문제를 단일 Density Shop 문제로 인코딩합니다. :

두 번째 문제는 Wang Dense Shop 문제에 관한 것입니다

타일 ​​세트 (단위 정사각형, 각 모서리에는 제한된 팔레트의 특정 색상이 할당됨), 인접한 타일이 공통 타일에서 동일한 색상을 갖도록 번역하여 표준 그리드 를 사용하여 평면을 테셀레이션하는 것이 가능합니까? 가장자리?

Berger는 이 질문을 결정할 수 없다는 유명한 결론을 내린 적이 있습니다.

다시 작성해야 할 내용은 Berger, Robert입니다.

이 질문을 상위 수준으로 변환하세요. 질문 차원 변환 단일 조밀 타일링 문제는 일부 중간 문제를 해결해야 합니다

우선, 우리는 Wang의 조밀 타일링 문제를 비슷한 문제, 즉 도미노 문제라고 부르는 문제에 쉽게 포함시킬 수 있습니다.

다음과 같이 다시 작성됨: 도미노 문제는 문제 3입니다.

한 쌍의 인접한 셀인 수평(또는 수직) 도미노 또는 의 유한 집합이 주어지면 정사각형, 각 단위 정사각형은 다음과 같습니다. 유한 집합의 요소 점으로 장식 표준 격자 타일 의 각 단위 사각형에 점을 할당하여 이 타일의 각 쌍이 수평(또는 수직) 사각형에서 도미노를 사용할 수 있도록 할 수 있습니까? 또는 ?

실제로 각 Wang의 타일을 별도의 "점"으로 삽입하고 도미노 세트 , 이 가로 또는 세로로 인접하도록 정의하기만 하면 되며 가장자리에는 Wang의 비밀 쌍이 있습니다. 같은 색.

다음 단계에서는 도미노 문제와 스도쿠 문제를 결합해 보겠습니다.

문제 4(스도쿠 문제)

열 너비 , 숫자 집합 , 함수 집합 및 "초기 조건" (여기서 자세히 설명하지 않음) "스도쿠 보드" 의 각 셀 에 숫자 을 할당하여 모든 경사면 및 가로채기 에 사용할 수 있습니까? 선에 있는 숫자 는 에 있습니다(그리고 는 초기 조건 을 따릅니다)?

이 논문의 가장 참신한 부분은 도미노 문제가 실제로 스도쿠 문제에 포함될 수 있음을 증명하는 것입니다.

스도쿠 문제를 하나의 비밀 퍼즐에 포함시키는 것은 이전 논문에서 제안한 수정된 방법을 기반으로 합니다.

이 논문에서도 스도쿠 문제의 다른 버전을 제안하고 "암호 퍼즐"이라는 방법을 만들었습니다. 패딩 언어"는 다양한 문제(스도쿠 문제 포함)를 단일 포장 문제로 변환할 수 있습니다

도미노 문제를 스도쿠 문제로 인코딩하려면 도미노 함수를 얻어야 합니다

( 일부 도미노 세트 ) 이를 사용하여 스도쿠 기능 을 구축합니다(도미노 세트와 관련된 일부 스도쿠 제약 조건 준수). 반대로 각각은 숫자를 따릅니다. 스도쿠 퍼즐 규칙의 스도쿠 기능은 도미노에서 생성되어야 합니다. 어떤 방식으로든 기능합니다.

이 접근 방식은 즉시 명백하지는 않지만 Tao와 Rachel Greenfeld는 Emmanuel Jeandel의 도움을 받아 Aanderaa와 Lewis의 일부 아이디어를 적용했으며 특정 계층 구조를 사용하여 한 문제를 다른 문제로 인코딩했습니다.

여기서 계층 구조를 설명합니다 (도미노 문제의 2차원 특성으로 인해 두 개의 서로 다른 소수를 사용해야 함).

그런 다음 일종의 임베딩을 구현하는 공식 을 통해 을 사용하여 스도쿠 함수 를 구축하세요.

여기서 는 두 개의 서로 다른 큰 소수입니다(예: , 을 사용할 수 있음). 는 을 로 나눈 횟수를 나타냅니다.

은 확장의 마지막 0이 아닌 숫자입니다.

(

및 ).情况의 경우 (1)의 첫 번째 구성 요소는 다음과 같습니다.

최종 가중치 의 일반적인 예는 다음과 같습니다.

흥미롭게도 어떤 이유에서인지 , 여기 장식은 기본적으로 어린이 게임 "Fizz buzz"의 규칙을 따릅니다.

위 내용은 테렌스 타오(Terence Tao)가 또 다른 60년 기하학 문제에 접근합니다! 주기적인 밀착 포장 문제에 새로운 돌파구가 마련되었습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!