Terence Tao nähert sich einem weiteren 60-jährigen Geometrieproblem! Beim Problem der regelmäßigen Nahtpflasterung wurde ein neuer Durchbruch erzielt

Tao Zhexuan hat einen neuen Durchbruch bei der Untersuchung des periodischen Kachelproblems erzielt

Am 18. September haben Tao Zhexuan und Rachel Greenfeld das Preprint-Papier „Undecidability of translatoral monotilings“ auf arXiv hochgeladen.

Papieradresse: https://arxiv.org/abs/2309.09504

Die Hauptschlussfolgerung dieses Papiers ist, dass, wenn die Dimension des Gitters unbegrenzt ist, dann die endliche Unterteilung des Gitters bestimmt werden muss Die Frage, ob eine Menge eine periodische Teilmenge des Gitters kacheln kann, ist unentscheidbar

Wissen Sie, dieses Problem ist in Dimension 1 und Dimension 2 entscheidbar.

Tao Zhexuan sagte, es sei etwas seltsam, dass die meisten der in dem Artikel gezeigten Komponenten beliebten Spielen ähneln –

Die Kachelanaloga von Domino, Sudoku, dem Computerspiel „Tetris““ , sogar das Kinderspiel „Fizz Buzz“ erschien

Warum erfordert das Lernen einer Matheaufgabe so viele Spiele? Tao Zhexuan kann auch die Unentscheidbarkeit der translatorischen einzelnen dichten Kacheln nicht erklären. Dieser Artikel ist eine Fortsetzung des vorherigen Artikels der beiden. Link Periodic Tile Problem

In der letzten Arbeit konstruierten sie eine translatorische einzelne dichte Kachelung eines hochdimensionalen Gitters

(eine einzelne dichte Kachelungist also ein endliche Menge), es ist nicht periodisch (es gibt keine Möglichkeit, diese Kachelung in eine periodische Kachelung zu „fixieren“, wobei

jetzt periodisch in Bezug auf die endliche Indexuntergruppe

ist).Diese Tatsache widerlegt die Hypothese von Stein, Grunbaum-Shephard und Lagarias-Wang über die Nichtexistenz aperiodischer dicht gepackter Monomere(„Hat single dicht gepackt“ ist ein kürzlich entdecktes aperiodisches isometrisches Single dichte Kacheln

, bei denen Drehung, Reflexion und Translation zulässig sind, oder der neuere „Geistermonolith“ ähnelt der einzelnen dichten Kachelung, ist jedoch nicht erforderlich.

Einer der Gründe, warum Tao Zhexuan und Rachel Greenfeld diese Vermutung inspirierten, ist die Beobachtung des Mathematikers Hao Wang

Er fand heraus, dass, wenn die periodische Kachelvermutung wahr ist, das translatorische Kachelproblem algorithmisch bestimmbar ist ——

Es gibt eine Turingmaschine für, bei gegebener Dimensionund einer endlichen Teilmengekann in begrenzter Zeit bestimmt werden, obtesseliert werden kann. Das liegt daran, dass periodische Kacheln über eine Computersuche gefunden werden können subs Mengen, diese Teilmengen können nicht durch

disjunkte Übersetzungen abgedeckt werden, die auch durch Computersuche entdeckt werden können.

Die periodische Tessellationsvermutung besagt, dass dies die einzigen zwei möglichen Situationen sind, und gibt somit Entscheidbarkeit vor.Andererseits ist Wangs Standpunkt unveränderlich: Das Scheitern der periodischen Tessellationsvermutung bedeutet nicht automatisch die Unentscheidbarkeit des translatorischen Einzeltessellationsproblems, da es die Existenz anderer Algorithmen nicht ausschließt Bestimmen Sie die Tessellation. Diese Tessellation kann unabhängig von der Existenz einer periodischen Tessellation sein

(zum Beispiel auch mit der neu entdeckten Hut- und Geister-Tessellation für den isometrischen Simplex von Polygonen mit rationalen Koeffizienten in

Es bleibt offen Frage, ob das Problem der dichten Kachelung mit oder ohne Reflexion entscheidbar ist

Die Hauptergebnisse dieser Arbeit befassen sich mit diesem Problem (mit einer Einschränkung):

Der schriftliche Inhalt ist: Satz 1

Es gibt keinen Algorithmus für

, bei gegebener Dimension

, einer periodischen Teilmenge

und einer endlichen Teilmenge

. Bestimmen Sie, ob ein Schwenken vorliegtim Inneren eine begrenzte Zeit.

Es ist wichtig zu beachten, dass man eine periodische Teilmengevonund nicht alleverwenden muss; dies liegt größtenteils an den technischen Einschränkungen dieses Ansatzes und lässt sich wahrscheinlich durch zusätzlichen Aufwand und Kreativität erreichen zu beseitigen.

Darüber hinaus bemerkten Terence Tao und Rachel Greenfeld auch, dass beidie periodische Pflastervermutung von Bhattacharya aufgestellt wurde, sodass das Problem in diesem Fall entscheidbar ist.

Für jeden festen Wert vonist noch offen, ob das Kachelproblem entscheidbar ist (beachten Sie, dass im obigen Ergebnis die Dimensionnicht fest, sondern Teil der Eingabe ist).

Aufgrund des bekannten Zusammenhangs zwischen algorithmischer Unentscheidbarkeit und logischer Unentscheidbarkeit (auch als logische Unabhängigkeit bekannt) impliziert dieser Satz auch die Existenz einer (im Prinzip eindeutig beschreibbaren) DimensionDer periodischen Teilmengenvon,und die endliche Teilmengevonlassendie Übersetzungskachelungbestehen und können in der ZFC-Mengentheorie weder bestätigt noch verfälscht werden (natürlich vorausgesetzt, die Theorie ist konsistent).

Aufgrund dieses Ansatzes können wirhier auch durch die „fast zweidimensionale“ Gruppeersetzen, wobeieine endliche abelsche Gruppe ist (jetzt Teil der Eingabe, stattdessen Dimensionen).).

Beschreiben Sie als Nächstes einige der Hauptgedanken des Beweises.

Eine übliche Methode, um zu beweisen, dass ein Problem unentscheidbar ist, besteht darin, andere Probleme, von denen bekannt ist, dass sie unentscheidbar sind, in das ursprüngliche Problem zu „kodieren“, sodass jeder Algorithmus, der das ursprüngliche Problem bestimmt, auch das eingebettete Problem bestimmen kann

Deshalb kodieren wir das Wang-Dense-Shop-Problem als ein einzelnes Dense-Shop-Problem:

Das zweite Problem betrifft das Wang-Dense-Shop-Problem

Gegeben ein endliches Wang For a Satz von Kacheln(Einheitsquadrate, jeder Kante ist eine bestimmte Farbe aus einer begrenzten Palette zugewiesen), ist es möglich, die Ebene mithilfe eines Standardgittersdurch Übersetzung so zu tesselisieren, dass benachbarte Kacheln auf einer gemeinsamen Fläche die gleiche Farbe haben? Rand? Berger hat einmal die berühmte Schlussfolgerung gezogen, dass dieses Problem nicht bestimmt werden kann Das Problem der dimensionalen Übersetzung einzelner dichter Kacheln muss einige Zwischenprobleme lösen

Zunächst können wir das Problem der dichten Kachelung nach Wang leicht in ein ähnliches Problem einbetten, das wir Domino-Problem nennen:

Wie folgt umgeschrieben: Das Domino-Problem ist Problem 3

Gegeben sei eine endliche Menge horizontaler (oder vertikaler) Dominosteine

oder

, bei denen es sich um ein Paar benachbarter Zellen handelt. Quadratisch ist jedes Einheitsquadrat dekoriert mit einem Elementpunkt in der endlichen Menge

Ist es möglich, jedem Einheitsquadrat in der Standardgitterkachel

einen Punkt zuzuweisen, sodass jedes Paar in dieser Kachel horizontale (oder vertikale) Quadrate ausverwenden kannoder

?Tatsächlich müssen wir nur jede Wang-Kachel als separaten „Punkt“ einfügen und das Domino-Set,so definieren, dass es horizontal oder vertikal aneinander angrenzt und die Kanten Paare von Wang-Geheimnissen aufweisen der gleichen Farbe.In den nächsten Schritten kombinieren wir das Domino-Problem mit dem Sudoku-Problem:

Aufgabe 4 (Sudoku-Aufgabe)

Gegeben ist die Spaltenbreite, die Menge der Zahlen, die Menge der Funktionenund die „Ausgangsbedingungen“（ Hier möchte ich nicht auf Details eingehen): Ist es möglich, jeder Zelleim „Sudoku-Brett“eine Nummerzuzuweisen, sodass für jede Steigungund jeden SchnittpunktBefinden sich die Zahlenentlang der-Linie in(undgehorchen die Anfangsbedingungen)?

Der neuartigste Teil dieser Arbeit ist der Beweis, dass das Domino-Problem tatsächlich in ein Sudoku-Problem eingebettet werden kann.

Die Einbettung des Sudoku-Problems in ein einziges geheimes Rätsel basiert auf der modifizierten Methode, die in früheren Artikeln vorgeschlagen wurde.

„Padding Language“ kann verschiedene Probleme (einschließlich Sudoku-Probleme) in ein einziges Paving-Problem umwandeln.

Um das Domino-Problem in ein Sudoku-Problem zu kodieren, müssen wir eine Domino-Funktion erhalten ein Domino-Set

) und verwenden Sie es, um eine Sudoku-Funktion zu erstellen(befolgen Sie einige mit dem Domino-Set verbundene Sudoku-Einschränkungen); umgekehrt gehorcht jede der Zahl. Die Sudoku-Funktionen der Sudoku-Rätselregeln müssen aus dem Domino generiert werden irgendwie funktionieren.

Dieser Ansatz ist nicht sofort offensichtlich, aber Tao und Rachel Greenfeld haben mit Hilfe von Emmanuel Jeandel einige Ideen von Aanderaa und Lewis übernommen und bestimmte Hierarchien verwendet, um ein Problem in ein anderes zu kodieren.

Hier erklären wir die hierarchische Struktur(aufgrund der Zweidimensionalität des Dominoproblems müssen zwei verschiedene Primzahlen verwendet werden).

Dann bauen Sie die Sudoku-Funktionmitüber die Formelauf, die eine Art Einbettung verkörpert.

wobeizwei verschiedene große Primzahlen sind (zum Beispiel können Sie,nehmen),die Häufigkeit darstellt, mit derdurchgeteilt wird, und.

ist die letzte Zahl ungleich Null in der Erweiterung von:

(

und). Im Fall von 情况 ist die erste Komponente von (1) unten dargestellt:

Das typische Beispiel für das Endgewichtist unten dargestellt:

Interessanterweise aus irgendeinem Grund Die Dekoration folgt hier grundsätzlich den Regeln des Kinderspiels „Fizz Buzz“

Das obige ist der detaillierte Inhalt vonTerence Tao nähert sich einem weiteren 60-jährigen Geometrieproblem! Beim Problem der regelmäßigen Nahtpflasterung wurde ein neuer Durchbruch erzielt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!