Zeigen Sie, dass es unendlich mehr Probleme gibt, als wir jemals berechnen können

8

Ich habe mir diese Lesung des MIT über die Komplexität der Berechnungen angesehen und in Minute 15:00 beginnt Erik Demaine eine Demonstration, um zu zeigen, was im Titel dieser Frage steht. Ich kann seiner Argumentation jedoch nicht folgen. In der Praxis sagt er Folgendes:
Wir können ein Entscheidungsproblem als Zeichenfolge von 0 und 1 die in der Praxis die Wahrheitstabelle der Funktion ist.
Er fährt fort, dass ein Entscheidungsproblem eine unendliche Folge von Bits ist, während ein Programm eine endliche Folge von Bits ist und bis hier kein Problem darstellt. Was ich nicht verstehe, ist die Fortsetzung des Beweises von diesem Punkt an: Entscheidungsprobleme sind in R weil Sie einen Dezimalpunkt vor die Zeichenfolge setzen können, die das Problem darstellt, und so den Dezimalteil eines Real erhalten

 for example if you have 0111011010101010101... it could become x.0111011010101010101... 

Ein Programm ist "nur" eine ganze Zahl in N weil es eine endliche Folge von Bits ist. Der Punkt, den ich nicht verstehe, ist, wie es möglich ist, dass ein Entscheidungsproblem mit einer reellen Zahl anstelle einer ganzen Zahl vergleichbar ist ... Ich meine, wenn wir das Argument "einen Punkt vor die Zahl setzen" verwenden könnten, könnte dies nicht Die gleiche Überlegung gilt auch für die Anzahl der möglichen Algorithmen, die jemals erstellt werden können.

Yamar69
quelle
11
Der Punkt ist, dass die Anzahl der Algorithmen zählbar ist, während die Anzahl der Entscheidungsprobleme unzählbar ist. Ich schlage vor, diese Begriffe in einem Lehrbuch über elementare Mengenlehre nachzuschlagen.
Yuval Filmus
1
@ Yuval Filmus Ich bin mir der Bedeutung dieser Begriffe durchaus bewusst. Was ich nur schwer assimilieren kann, ist der Grund für diese unterschiedlichen Kardinalitäten (Algorithmen / Entscheidungsprobleme).
Yamar69
1
@JimmyB Die gleiche Aussage gilt für die rationalen Zahlen, aber die rationalen Zahlen sind immer noch zählbar (mit der gleichen "Größe" wie die ganzen Zahlen), während die reellen Zahlen dies nicht sind.
Gregory J. Puleo
1
Interessanter ist vielleicht, dass es unendlich viele endlich festgelegte Entscheidungsprobleme gibt, die von keiner Turing-Maschine entschieden werden können. Sie brauchen keinen Appell an unzählige Mengen, um zu dem Schluss zu kommen, dass es unendlich viele algorithmisch unlösbare Probleme gibt. Sie brauchen nicht die Unzählbarkeit der reellen Zahlen, um zu dem Schluss zu kommen, dass die Menge der berechenbaren reellen Zahlen eine unendliche Ergänzung hat.
John Coleman
1
"... als wir jemals berechnen können" legt nahe, dass die Probleme, die wir berechnen können, mit der Zeit variieren. Die Definition von "berechenbar" ist nicht zeitabhängig.
David Richerby

Antworten:

9

Wenn ich Sie richtig verstehe, lautet Ihre Frage: Warum kann eine Lösung durch eine natürliche Zahl und ein Problem mit einer reellen Zahl codiert werden? (Ich gehe davon aus, dass Sie die nächste Phase des Beweises verstehen, die auf dem Unterschied zwischen den Sätzen der Kardinalität c und basiert0 .)

Der Grund liegt in der Mengenlehre, insbesondere in der Kardinalität verschiedener Mengen. Zählen Sie die Anzahl der Programme - dies ist die Größe der verschiedenen Zeichenfolgen einer bestimmten Sprache oder eines bestimmten Zeichensatzes (z. B. ASCII). Diese Größe entspricht der Größe der Menge N. (natürliche Zahlen). (Jede Zeichenfolge kann als ihr Wert dargestellt werden, der durch ihre binäre Repräsentation berechnet wird.)

Zählen Sie jedoch die Anzahl der Funktionen von den natürlichen Zahlen (oder den Zeichenfolgen, die sie darstellen) bis {0,1}} zählt, ist das eine ganz andere Geschichte, und hier haben wir es mit Größenunterschieden zwischen zwei unendlichen Mengen zu tun. Die Größe dieses Sets ist größer. Es gibt einen schönen Beweis, der auf der Tatsache beruht, dass die Funktionen vonN. bis zu allen oben genannten Mengen nicht "auf" sein können, was zur Schlussfolgerung der Kardinalitätsdifferenz führt. Den Beweis können Siehierlesen.

Royashcenazi
quelle
11

Der Dozent versucht, mathematisch präziser umzuformulieren: Der Algorithmus kann (eindeutig) als endliche Bitfolge codiert werden, und jede endliche Bitfolge (eindeutig) codiert ein Programm. Daher gibt es eine Bijektion zwischen N. und dem Satz von Algorithmen, so dass beide zählbare Sätze sind. Umgekehrt kann, nachdem eine Reihenfolge von Zeichenfolgen festgelegt wurde, jedes Entscheidungsproblem P. (eindeutig) als eine unendliche Zeichenfolge von Bits codiert werden, wobei das ich te Bit darstellt, ob die ich te Zeichenfolge in P. oder nicht, und jede unendliche Zeichenfolge von Bits (eindeutig) codieren ein Entscheidungsproblem (auf die gleiche Weise); daher R. und die Menge der Entscheidungsprobleme beide unzählige Mengen.

dkaeae
quelle
6

Jeder Algorithmus kann durch eine endliche Zeichenfolge beschrieben werden, so dass es nur zählbar viele Algorithmen gibt. Im Gegensatz dazu können wir jedes Entscheidungsproblem als unendliche Dezimalstelle in Basis 2 beschreiben, und außerdem ist dies eine surjektive Abbildung: jede Zahl in [0,1]] kann in ein Entscheidungsproblem "decodiert" werden. Daher gibt es unzählige Entscheidungsprobleme.

Das Dekodierungsargument funktioniert nicht für Algorithmen - während jeder Algorithmus einer endlichen Dezimalstelle entspricht, deckt dies nicht alle [0,1]] , sondern nur eine zählbare Teilmenge davon.

Yuval Filmus
quelle