Sind Dateien aufgrund des Anhaltensproblems eigentlich unwissfähig?

Question

Wenn Sie beim Herunterladen einer Datei aus dem Internet auf unseren Computer heruntergeladen werden, werden in der Regel mit einer Schätzung dessen aufgefordert, wie lange es dauert, bis die Datei heruntergeladen werden soll.

aus dem Haltingproblem, wissen wir, dass $ \ mathrm {halt} _ {\ mathrm {tm}} $ unentgierig ist, wobei:

$ \ mathrm {halt} _ {\ mathrm {tm} _ {\ mathrm {tm}}={⟨m, w⟩ \ mid m \ text {ist ein tm und} m \ text { Hält am Eingang} w \} $

Angenommen, wir können das Fehlen eines unendlichen Speichers vernachlässigen können, können wir unseren Computer auf der Festplatte als Turing-Maschine als Turing-Machine $ M $ modellieren und die Zeichenkodierung von Die heruntergeladene Datei als Input $ W $ . (Genauer gesagt, $ W $ sollte die erhaltene Zeichenfolge sein, die die vom Netzwerk gesendeten Pakete ermittelt werden)

aus dem anhaltende Problem folgt, dass es nicht nur unmöglich ist, zu wissen, wann der Download enden wird, es ist sogar unmöglich zu wissen, ob der Download jemals enden wird.

Sind Sie also Dateien, die aufgrund des Anhaltensproblems tatsächlich unkenntlich sind? Wenn nicht, wo der obige Argumentation fehlschlägt?

Answer 1

überhaupt nicht.

Das Anhaltensproblem sagt, dass es unmöglich ist, zu entscheiden, ob eine willkürliche Turing-Maschine mit willkürlicher -Eineingabe hält.Es gibt jedoch viele, viele spezifische Turing-Maschinen, in denen wir nachweisen können, dass sie für jeden Eingang halt, oder wenn wir den Eingang anschauen und entscheiden können, ob die Turing-Maschine hält oder nicht.

Und seitdem die Leute, die den Downloadcode schreiben, sicherlich so geschrieben, dass es garantiert für jeden Import abgeschlossen ist, es wird ein Beweis dafür geben, dass es garantiert ist.

Answer 2

Das Hauptproblem, denke ich, ist, dass Sie Ihr unbekanntes Problem (Datei-Downloadzeiten) auf ein hartes Problem (das Anhaltensproblem) reduziert haben, das zeigt, dass, wenn Sie einen effizienten Algorithmus hatten, um das harte Problem zu lösen, dann das UnbekannteDas Problem wäre auch effizient lösbar.Um die Härte des unbekannten Problems zu erweisen, benötigen Sie eine Verringerung, die auf andere Weise geht, indem Sie zeigen, dass Sie das effizientes Lösen des unbekannten Problems ermöglichen, dass Sie das harte Problem effizient lösen können.

(ein sekundäres Thema ist, dass ich nicht wirklich sehe, um das Problem "Datei-Downloadzeit" ausdrücklich in Bezug auf abstrakte Turing-Maschinen auszudrücken, da das Problem selbst so im Wesentlichen an die physische Welt gebunden ist.)

Answer 3

Das Lösen der "Downloadzeitprobleme" ist einfach unmöglich.Nichts sagt, wenn Ihre Maschine (oder das Netzwerk oder der Ursprung oder ...) (oder nicht) abstürzt oder überlastet wird (vielleicht alle in Indien aufwachen, worzt der Drang, dieselbe Datei zu erhalten, und abstürzenServer) oder langsam zu einer Kriechung, oder beschleunigt sich einfach bis zu einer Brise, halb durch.

Das Problem hier ist, dass die tatsächliche Zeit von einer Myriard-Variablen abhängt, viele von ihnen unbekannt (und unkenntlich), aufgrund der immensen Komplexität des Internets und deren Millionen von Benutzern (und vielen anderen äußeren Faktoren, die sich auswirken könnenes funktioniert funktioniert).

Das anhaltende Problem für Turing-Maschinen ist ganz anders, da die Teile und ihre Beziehung klar, einfach und klar definiert sind.Mit dem Design, wirklich: Turing suchte nach einem transparenten Modell dessen, was es bedeutet, dass ein Mensch etwas "Berechnen Sie etwas, und destilliert sie auf ein extrem minimales, einfaches.