Was sind sehr kurze Programme mit unbekanntem Stoppstatus?

32

Dieses 579-Bit-Programm im binären Lambda-Kalkül hat einen unbekannten Haltestatus:

01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

Das heißt, es ist nicht bekannt, ob dieses Programm beendet wird oder nicht. Um es zu bestimmen, müssen Sie die Collatz-Vermutung lösen - oder zumindest für alle Zahlen bis zu 2 ^ 256. In diesem Repository finden Sie eine vollständige Erklärung, wie dieses Programm erhalten wurde.

Gibt es (viel) kürzere BLC-Programme, die ebenfalls einen unbekannten Stoppstatus haben?

MaiaVictor
quelle
6
Sehr verwandte Frage . Gemeinschaftsstimmen, bitte: Duplizieren?
Raphael
9
Die Aufgabe ein solches Programm zur Expression in möglichst wenigen Bits wie möglich scheint ein Fragen zu sein Code Golf , weniger Computer Wissenschaft .
Raphael
2
Ich denke, dass Rickys Antwort zu 5-State-TMs besser ist als die Antwort auf die ursprüngliche Frage. Kann die Antwort verschoben werden, wenn diese als Betrug geschlossen wird?
David Richerby
6
Ihnen fehlt ein wichtiges Detail: Sie haben nicht angegeben, in welcher Sprache das Programm geschrieben werden muss. In Ihrem Beispiel wird eine binäre Lambda-Rechnung verwendet - ist das die einzige Sprache, die Sie interessiert? Wir können sehen, dass es trivial ist, ein 1-Bit-Programm mit unbekanntem Haltestatus zu entwickeln, indem einfach der Rumpf des Algorithmus direkt in die Sprache selbst eingebettet wird. Es ist eine Lücke, aber eine, auf die Sie achten müssen, wenn Sie nach Golflösungen fragen. Sie lieben ihre Schlupflöcher! Die Komplexität von Kolmogov kann hier ein wichtiges Thema sein.
Cort Ammon - Reinstate Monica

Antworten:

30

Ja. Diese Seite sagt , es gebe 98 5-Zustand sind Turingmaschinen sind , deren Haltestatus unbekannt. Ärgerlicherweise gibt es keine Beispiele für solche Maschinen, aber diese 26 Jahre alte Seite enthält 2 Turing-Maschinen mit 5 Zuständen, deren Stoppstatus zu diesem Zeitpunkt anscheinend unbekannt war. (Wenn Sie nach "simple counter" suchen, werden Sie direkt zwischen diesen 2 weitergeleitet.) Ich habe sie hier kopiert, falls der Link ausfällt:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L

quelle
Am Ende der Seite steht: $ Date: 2007/11/03, wie ist es dann 26 Jahre alt?
Falaque
1
@Falaque Am oberen Rand der Seite steht "Diese Seite ist die HTML-Neufassung des Autors vom ... Februar 1990". Der Text ist 26 Jahre alt, die HTML-Wiedergabe stammt von (oder wurde zuletzt aktualisiert) im Jahr 2007.
IMSoP
5

Collatz-Vermutung:

Das folgende Programm hält immer an:

void function( ArbitraryInteger input){
     while( input > 1){
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }

     // Halt here
}

Leichte Variation (immer noch eine Vermutung, da sie auf einem Ergebnis von Collatz basiert):

Bei einigen Eingaben wird das folgende Programm niemals zweimal in denselben Zustand versetzt (wobei der Zustand durch den Wert bestimmt wird, der von "input" gespeichert wird):

void function( ArbitraryInteger input){
     while( input >= 1){ // notice the "="
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }
}

Beachten Sie, dass das zweite Programm niemals anhält, unabhängig davon, ob das erste Programm anhält oder nicht.

Es wird angenommen, dass das erste Programm für jede Eingabe immer beendet wird, wir haben jedoch keinen Beweis dafür, und es gibt möglicherweise noch eine ganze Zahl, für die das Programm nicht angehalten wird (es gibt auch einen Preis von 100 USD für den Beweis dafür). .

Das zweite Programm ist ebenfalls interessant: Es besagt, dass das Programm für einige Eingaben niemals zweimal in den gleichen Zustand wechselt, was im Grunde voraussetzt, dass das erste Programm eine Sequenz aufweist, von der bekannt ist, dass sie ohne Wiederholung auseinander läuft. Es erfordert nicht nur, dass die Collatz-Vermutung falsch ist, sondern es erfordert, dass sie falsch und ohne Schleifen ist , abgesehen von der offensichtlichen 1,4,2,1-Schleife.

  • Wenn Collatz nur Gegenbeispiele für Schleifen hat, ist die Abweichung von der Vermutung falsch

  • Wenn Collatz ohne Schleifen falsch ist, ist die Variation der Vermutung wahr

  • Wenn Collatz wahr ist, ist die Variation falsch

  • Wenn Collatz falsch ist, weil es Schleifen hat und weil es eine Zahl hat, für die es divergiert, ist die Variation der Vermutung wahr (es ist nur eine Zahl erforderlich, für die es divergiert, ohne eine Schleife einzugeben).

Ich denke, die Variante ist interessanter (nicht nur, weil ich sie durch Zufall gefunden und dank @LieuweVinkhuijzen bemerkt habe), sondern weil es tatsächlich eines echten Beweises bedarf. Durch brachiales Forcen können wir möglicherweise eines Tages eine Schleife finden (und das wird eine Schleife sein, die länger als 70 Nummern ist: Nach dem gegenwärtigen Stand der Technik können keine Endlosschleifen kürzer als 68 oder so sein), und brutal Erzwingen ist nicht interessant: Es ist nur das Knacken von Zahlen. Wir können jedoch eine unendliche divergierende Sequenz nicht brachial erzwingen, wir wissen nicht, ob sie wirklich ohne einen echten Beweis enden wird.

EDIT: Ich habe den Teil über Collatz Conjecture übersprungen. Entschuldigung, ich habe wirklich auswendig mit einem Algorithmus geantwortet, den ich vor einigen Jahren gelesen habe. Ich habe nicht erwartet, dass das bereits erwähnt wurde.

EDIT2: Ein Kommentar hat mich darauf aufmerksam gemacht, dass ich den Algorithmus mit einem Fehler geschrieben habe. Dieser Fehler unterscheidet meine Antwort jedoch von der Collatz-Vermutung (aber eine direkte Variation davon).

Spielentwickler
quelle
1
Ich denke du meinst schreiben input > 1statt input >= 1? Wie es jetzt ist, wird dieses Programm1421
Lieuwe Vinkhuijzen am
Sie haben Recht, ich wollte ein setzen >, aber solange wir keinen Beweis für Halt >haben, können wir nicht sicher sein, ob wir die 1 -> 4 -> 2 -> 1Schleife erreichen werden (zum Beispiel, wenn es nicht endet, weil >es nicht funktioniert ). t reach >=)
GameDeveloper
1
Ein Beweis deines Programms mit hält nicht an: Angenommen die Collatz-Vermutung ist wahr, dann erreichen wir die Schleife bei allen Eingaben. Andernfalls, wenn es falsch ist, erreichen wir die Schleife an einigen Eingängen, und an anderen Eingängen schleift die Sequenz entweder an einer anderen Stelle oder sie divergiert ins Unendliche (und schleift daher für immer). In beiden Szenarien stoppt das Programm mit niemals, unabhängig davon, ob Collatz 'Vermutung wahr ist oder nicht. Das Programm mit stoppt bei allen Eingaben, wenn die Collatz-Vermutung wahr ist, was nicht geklärt ist. >=14211421>=>
Lieuwe Vinkhuijzen
2
Es gibt einen viel einfacheren Beweis dafür, dass das zweite Programm nicht anhält, wodurch das Collatz-Theorem nicht als bedingtes Ergebnis aufgerufen wird. Das Programm wird angehalten, wenn . Aber keiner der beiden Fälle wird das bewirken. Wenn , wird zu . Wenn , wird eine andere Zahl, die größer oder gleich . In jedem Fall wird nie unterschritten , was zum Beenden der Schleife erforderlich ist. Ich verstehe deinen letzten Kommentar nicht. n<1n=1n4n>1n11
Lieuwe Vinkhuijzen
1
Das ist wahr :) Du hast recht, ich hätte meinem ersten Kommentar hinzufügen sollen, wenn die Collatz-Vermutung wahr ist. Ich sehe deine Bearbeitung sehr gut. Sie brauchen das zweite Programm nicht, weil die Vermutung, dass dieses Programm niemals zweimal in denselben Zustand übergeht, auch für das erste Programm ungelöst ist: Möglicherweise gibt es eine Zahl, die nicht ins Unendliche abweicht, sondern in a steckt große Schleife irgendwo in sehr hohen Zahlen.
Lieuwe Vinkhuijzen