Ein einfaches Problem, dessen Entscheidbarkeit nicht bekannt ist

Ich bereite mich auf einen Vortrag vor, der sich an Bachelor-Mathematiker richtet, und als Teil davon denke ich darüber nach, das Konzept der Entscheidbarkeit zu diskutieren. Ich möchte ein Beispiel für ein Problem geben, von dem wir derzeit nicht wissen, dass es entscheidbar oder unentscheidbar ist. Es gibt viele solche Probleme, aber keines scheint bisher als gutes Beispiel hervorzuheben.

Was ist ein einfach zu beschreibendes Problem, dessen Entscheidbarkeit offen ist?

Das Matrix Mortality Problem für 2x2 Matrizen. Das heißt, wenn eine endliche Liste von 2 × 2 Ganzzahlmatrizen M ₁ , ..., M _{k gegeben ist} , können die M _i in einer beliebigen Reihenfolge (mit beliebig vielen Wiederholungen) multipliziert werden, um die All-0-Matrix zu erzeugen?

(Der 3x3-Fall ist bekanntermaßen unentscheidbar. Der 1x1-Fall ist natürlich entscheidbar.)

UPDATE: Das hier erwähnte Problem ist jetzt als unentscheidbar bekannt! http://arxiv.org/abs/1605.05274 Darüber hinaus wurde das Papier durch das Lesen dieser Antwort inspiriert. :)

Programmierer in Ihrem Fachpublikum werden überrascht sein, dass die Frage "Ist dieser Typ implizit auf diesen Typ konvertierbar?" Es ist nicht bekannt, dass Java 5, C # 4 und Scala 2 entscheidbar sind.

Weitere Einzelheiten finden Sie in Andrew Kennedys und Benjamin Pierces Aufsatz "Über die Entscheidbarkeit der nominalen Subtypisierung mit Varianz" . Der Aufsatz enthält einige Beispiele für zusätzliche Einschränkungen der Typsysteme dieser Sprachen, unter denen die nominelle Untertypisierung als entscheidbar oder als unentscheidbar bekannt wird.

Interessanterweise wurde das Papier lange vor dem Hinzufügen von generischer Kovarianz und Kontravarianz zu C # geschrieben, aber die Autoren haben die Richtung, in die sich die Sprache bewegte, richtig vorausgesehen. (Dies ist nicht überraschend. Die Autoren haben die zugrunde liegende Unterstützung für die Varianz in der CLR entworfen, die ich beim Hinzufügen von Varianz zu C # ausgenutzt habe. Sie haben das schwere Heben ausgeführt.)

Hilberts zehntes Problem über Rationalitäten: "Hat diese Polynomgleichung eine rationale Lösung?"

Nimmt das Problem einer linearen Wiederholung zusammen mit den Anfangswerten den Wert 0 an?

Zwei referenz:

http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/

http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

Ein einfaches Problem, dessen Entscheidbarkeit unbekannt ist, ist das folgende (ich denke, es ist noch offen):

Unendliches Schach :

Eingabe : Eine endliche Liste von Schachfiguren und deren Startpositionen auf einem Schachbrett; Frage : Kann sich White Force paaren?$Z \times Z$

Wenn wir die Bedingung hinzufügen, dass Weiß sich in Zügen paaren muss ( ist Teil der Eingabe), wird es entscheidbar: siehe Dan Brumleve, Joel David Hamkins und Philipp Schlicht, Das Paar-in-n-Problem des unendlichen Schachs ist entscheidbar .$n$$n$

Ein weiteres einfaches Problem ist das Verhalten von Langtons Ameise bei endlicher Erstkonfiguration.

Langtons Ameisenverhalten mit endlicher Unterstützung :

Quadrate in einer Ebene sind unterschiedlich schwarz oder weiß gefärbt. Wir identifizieren willkürlich ein Quadrat als "Ameise". Die Ameise kann sich bei jedem Schritt in eine der vier Hauptrichtungen bewegen. Die Ameise bewegt sich nach folgenden Regeln:

• Drehe an einem weißen Quadrat um 90 ° nach rechts, drehe die Farbe des Quadrats um und gehe eine Einheit vorwärts
• Drehe dich an einem schwarzen Quadrat um 90 ° nach links, drehe die Farbe des Quadrats um und gehe eine Einheit vorwärts

Eingabe : eine endliche Konfiguration (schwarz / weiß) der Ebene und der Ameisenposition;
Frage : Beendet die Ameise immer wieder den Bau einer unendlichen "Autobahn"?

Für unendliche Unterstützung ist das Problem nicht zu entscheiden, siehe: A. Gajardo, A. Moreira und E. Goles, Komplexität von Langtons Ameise

Das Collatz-Problem ist ein einfach zu beschreibendes Problem, dessen Entscheidbarkeit offen ist. Es handelt sich um eine einfache Wiederholung elementarer arithmetischer Operationen.

n / 2 3 n + $f(n)=\mathsf{\{}$ $n/2$ für gerade Ganzzahl, für ungerade Ganzzahl$3n+1$

Das Problem besteht darin, zu entscheiden, ob die Iteration dieser Funktion für eine bestimmte positive ganze Zahl immer auf 1 zurückkehrt .$n_0$

Interessanterweise erwies sich eine Verallgemeinerung des Collatz-Problems als unentscheidbar.

Verweise:

1- UNBEKANNTE PROBLEME: EIN SAMPLER , BJORN POONEN

2- Weisstein, Eric W. "Collatz Problem." Aus MathWorld - Eine Wolfram-Webressource.

3- Das 3X + 1-Problem: Ein Überblick , Jeffrey C. Lagarias

Es ist nicht bekannt, ob es entscheidend ist, ob eine gegebene Form die Ebene kacheln kann oder nicht .

Die Entscheidbarkeit der Conjunctive Query Containment ist seit über zwanzig Jahren offen. Die Lösung dieses Problems wäre ein Durchbruch in der Datenbanktheorie.

$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$

In konjunktiven Abfragen werden existenziell quantifizierte Prädikate mit AND verknüpft. In SQL-Begriffen handelt es sich bei konjunktiven Abfragen um SELECT-FROM-WHERE-Abfragen, die "=" und "AND" verwenden, jedoch keine Unterabfragen oder Aggregationen. Dies ist möglicherweise die häufigste Art von Datenbankabfragen und umfasst die meisten Suchmaschinenabfragen.

$I$$Q_1$$Q_2$

$\ne$

$(N,+,\times)$$(N,+,\times)$

Hinweise auf die umfangreiche Literatur und eine strenge Behandlung finden Sie in einem ToDS-Papier (in der Presse) von einigen Personen.

$Q$$R$$Q$$Q \text{ AND } R$$Q$

Korrespondenzproblem der Post mit einer festen Anzahl von Kacheln zwischen 3 und 6.

Es ist nicht wirklich einfach zu beschreiben, hat aber eine sehr "spielerische" Beschreibung und eignet sich meiner Meinung nach für Gespräche auf Intuitionsebene.

Das verallgemeinerte Problem der Sternhöhe: "Wie viele Nistplätze von Kleene-Sternen muss ich haben, um diese reguläre Sprache mit einem regulären Ausdruck zu repräsentieren, der eine Ergänzung zulässt?"

Wir wissen nicht einmal, ob der Algorithmus, der immer 1 zurückgibt (außer 0 für sternlose Sprachen, was ein entscheidbarer Fall ist), korrekt ist.

Ein Problem aus der Automatentheorie.

$D$

$x$$D$$x$$x$$L(D) \cap Primes$

Kommentar: Ich habe dieses Problem ursprünglich aus einer Stapelaustausch-Antwort von Jeffrey Shallit gehört. Wenn Sie Hinweise darauf kennen, lassen Sie es mich bitte wissen. Danke!

Zusammenhängende Posts:

(1) Gibt es noch offene Probleme mit DFAs?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Verwandte Arbeiten: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

"Minimale Elemente für die Primzahlen" von C. Bright, R. Devillers und J. Shallit

Iterierte Karten zum Intervall (Beschreibung von hier ):

(sehr verwandt mit dem von Magnus Find vorgeschlagenen Problem)

$F$$x$$x$$x$$F(x)$$F(F(x))$$F$$x$$F$

$F$$x$$y$$x$$y$

$F$

$F$$x$$y$$x$$F$

Ein Hinweis: Asarin 2011 .

Es scheint einen ziemlich natürlichen Weg / Winkel zu geben, um diese Frage zu untersuchen, der in mindestens 3 Arbeiten wie folgt verwendet wird.

$TM(k,l)$$k$$l$$k,l$$k,l$

Die Ergebnisse können wie in einigen der folgenden Verweise in einem Raster angezeigt werden. auch im Zwischenbereich ist bekannt, dass einige (ungelöste) Maschinen in der Lage sind, die Collatz-Vermutung für einige Eingaben zu simulieren.

daher gibt es hier eindeutig "Übergangspunkt" -ähnliche Phänomene, die jedoch nicht innerhalb einer berechenbaren Region ablaufen, sondern in einem ungewöhnlichen Sinne zwischen berechenbar und nicht berechenbar.

• Kleine Turingmaschinen und allgemeiner vielbeschäftigter Biberwettbewerb Michel

• Die Komplexität kleiner universeller Turingmaschinen: eine Übersicht Woods, Neary

• An den Grenzen der Lösbarkeit und Unlösbarkeit in Tag-Systemen. Theoretische und experimentelle Ergebnisse De Mol

$2^8$

Auch als Beispiel für ein "Beinahe-Unglück" oder eine "offene Frage, die vor kurzem als TM vollständig gelöst wurde", wurde die Wolfram 2,3-Maschine 2007 für einen 25.000-Dollar-Preis als universell erwiesen . Der Wettbewerb wurde im Mai 2007 angekündigt und der Gewinner Smith im Oktober 2007 .

Es gibt einen ziemlich natürlichen Weg, die meisten offenen Probleme auf Fragen der (Un-) Entscheidbarkeit abzubilden. Die meisten offenen Probleme sind im Allgemeinen nicht nachweisbar oder unbeweisbar.

Im Internet gibt es einige informelle Verwirrung über die Unentscheidbarkeit des P-gegen-NP- Problems, die nicht unbedingt ein Entscheidungsproblem darstellt. Daher ist es technisch nicht korrekt, über seine Unentscheidbarkeit zu sprechen. Andererseits scheint es einen engen / natürlichen Zusammenhang zwischen Unentscheidbarkeit und Beweisbarkeit zu geben.

zum Beispiel betrachten

$L$$x$$O(n^x)$

ist diese sprache entscheidbar Das ist eine Frage zu einer Sprache mit offener Entscheidbarkeit, die im Grunde eng mit dem P-gegen-NP-Problem und seiner inhärenten (Un-?) Beweisbarkeit verbunden (sogar, praktisch identisch) ist.

Für P vs NP als "einfach zu beschreiben" sind nur Konzepte von TMs , Big O-Laufzeitnotation und Nichtdeterminismus erforderlich , die relativ einfach sind (einige der grundlegendsten Konzepte von TCS) und auf der Ebene der Studenten unterrichtet werden oder die begabt sind Schüler konnte verstehen.

Tatsächlich ist NP vs P / Poly auch offen und kann auf die gleiche Weise auf eine offene Frage zur Entscheidbarkeit abgebildet werden, und dies kann als ein ziemlich einfaches Problem hinsichtlich des Wachstums von minimalen (monotonen?) Schaltkreisen zur Erkennung von NP complete angegeben werden Probleme (zB Cliquen).