Was ist ein Beispiel für ein rechnerisch unmögliches Geschäftsproblem?

17

Ich habe einen Kollegen, der sich weigert, die Tatsache zu akzeptieren, dass Turing-Maschinen (und von Neuman-Maschinen im weiteren Sinne) ihr eigenes Stopp-Problem nicht lösen können.

Sie können alles mit genug Zeit und Geld tun.

Er mag auch keine theoretischen Probleme, wenn er argumentiert, dass:

Auf unserem Gebiet werden wir niemals auf diese Fragen stoßen. Wir sind Anwendungsentwickler, keine theoretischen Wissenschaftler.

Gibt es ein gutes Beispiel für ein Geschäftsproblem, das rechnerisch unmöglich ist und das ich verwenden könnte, um ihn davon zu überzeugen?

Jesan Fafon
quelle
11
Sie können nicht durch ein Beispiel demonstrieren, dass etwas unmöglich ist. Ihr Kollege wird nur sagen "Es funktioniert nicht, weil wir nicht den richtigen Ansatz gefunden haben". Das Beste, was Sie tun können, ist ihm einen Beweis zu zeigen. Wenn er es nicht kauft, ist er entweder wirklich dumm oder ein Idiot oder beides. Hier ist eine Liste unentscheidbarer Probleme: en.wikipedia.org/wiki/List_of_undecidable_problems
Thomas Eding
18
Einer Theoretikerin und einem Ingenieur wurde gesagt, sie könnten ein Mädchen küssen, indem sie die Distanz zwischen sich und ihr mehrmals um die Hälfte zurücklegen. Der Theoretiker gab sofort auf und sagte: "Es ist unmöglich, ich werde nie dort hin kommen." Der Ingenieur sagte: "Ich werde für praktische Zwecke nah genug dran sein." Sie, Sir, müssen diesen Kuss versuchen.
Gbjbaanb
2
@gbjbaanb: Das ist ein guter Deskriptor für viele der nicht optimalen Lösungen für NP-harte Probleme, und zu wissen, dass diese Probleme (praktisch) klassisch nicht zu lösen sind, ist der Grund , warum Sie sich für die alternative Methode entscheiden. Wenn Sie nicht akzeptieren, dass einige Probleme praktisch oder buchstäblich unmöglich zu lösen sind, werden Sie nicht nach unvollkommenen Lösungen suchen, die nach einer unbestimmbaren Zeitspanne eine "ausreichend gute" Antwort geben können.
Phoshi
3
@Phoshi Nein, der Punkt ist, dass reale technische Lösungen nur eine Lösung erfordern, die gut genug ist, um das Problem ausreichend für die Akzeptanz zu lösen. Das perfekte Lösen lohnt sich nicht. z.B. Das Problem des Handlungsreisenden ist bei mehr als wenigen Knoten unmöglich, aber viele Unternehmen benötigen (und liefern) immer noch eine nicht optimale Lösung. Wenn wir nur Perfektion produzieren würden, hätte niemand diese.
gbjbaanb
10
@gbjbaanb: Stimmt, aber der einzige Grund, warum sie diese Probleme gelöst haben, ist zu akzeptieren, dass man mit genügend Zeit und Geld nichts anfangen kann und aufgehört hat, nach der optimalen Lösung zu suchen. Das Wissen darüber, was Sie nicht können , ist für die Lösungsfindung oft genauso wichtig wie das Wissen darüber, was Sie können .
Phoshi

Antworten:

11

Nicht technisch unmöglich, aber ...

Planen von Ressourcen mit dem Ziel, den idealen Zeitplan zu finden, der die Nutzung von Zeitfenstern maximiert. Ich war einmal in einem Projekt, in meinen früheren Computertagen, das diese Anforderung hatte. Ich habe eine Weile daran gearbeitet, bevor mir klar wurde, dass es NP-schwer ist.

Weitere Beispiele für Probleme, die technisch nicht unmöglich, aber technisch schwierig sind, finden Sie hier .

Die meisten harten Rechenprobleme im Business Computing sind nicht unmöglich, nur unpraktisch. Dein Freund hat recht; Sie können die meisten von ihnen lösen, wenn Sie genug Geld auf sie werfen. Aber das Argument ist fadenscheinig; Der springende Punkt bei der Führung eines Unternehmens ist, Geld zu verdienen und es nicht zu verlieren.

In der täglichen Praxis sprechen wir auf vage Art und Weise über die Vollständigkeit von Turing, nicht um ein mathematisches Prinzip zu demonstrieren, sondern um (zum Beispiel) die Unzulänglichkeit von HTML und CSS als komplettes Vehikel für die Erstellung von Programmen mit vollständigen Funktionen zu veranschaulichen.

In ähnlicher Weise ist das Problem des Anhaltens für Theoretiker wichtig, hat jedoch für die meisten Unternehmen keine große Relevanz.

Robert Harvey
quelle
14
Das Problem der Unterbrechung tritt bei der statischen Analyse von Code auf. Daraus können sich weltliche Probleme ergeben wie "Hier ist Code, mach es hübsch" bis "Hier ist Code, ist es Malware" - das erste ist geschäftlich wichtig für Unternehmen, die IDEs erstellen (Syntaxhervorhebung, Refactoring), das zweite bis Antiviren-Unternehmen und Sicherheitsexperten.
12
"In ähnlicher Weise ist das Problem des Anhaltens für Theoretiker wichtig, hat aber für die meisten Unternehmen keine große Relevanz.": Wenn das Problem des Anhaltens berechenbar wäre, könnten wir automatisch überprüfen, ob eine Software beendet wird oder hängen bleibt eine bestimmte Eingabe oder nicht. Wir hätten wahrscheinlich keinen BSOD mehr. Da dies nicht möglich ist, müssen wir andere Techniken anwenden, um die Qualität der Software zu gewährleisten (z. B. Testen), und niemand investiert Zeit und Geld, um ein allgemeines "Termination Check" -Programm zu entwickeln. Ich denke, dieses theoretische Ergebnis hat eine enorme praktische Relevanz.
Giorgio
4

Andere haben dies kommentiert, aber ich werde versuchen, eine Antwort zu schreiben, die meinen Standpunkt wiedergibt.

Ich mag die Antwort von Robert Harvey und die Kommentare zu seiner Antwort, und ich möchte auf diese eingehen.

Ich denke, Sie müssen diese unentscheidbaren Probleme (wie die Beendigung) auf eine banale Art und Weise darstellen: Zum Beispiel ein IDE-Tool, das "prüft, ob diese Funktion immer einen Wert zurückgibt".

Mein Lieblingsbeispiel beim Unterrichten war das Refactoring ( Funktionsäquivalenz, ein weiteres unentscheidbares Problem ). Ich fragte:

Wie überprüfen Sie, ob eine Funktion / ein Programm nach Ihrem netten Refactoring dasselbe tut? Natürlich haben wir Unit-Tests dafür, aber sie decken nicht alle Fälle ab. Und es ist langweilig zu schreiben ... Aber wir sind Programmierer! Wir sollten ein Programm schreiben, das prüft, ob diese beiden Funktionen immer das gleiche Ergebnis liefern! Warum versuchst du nicht, es zu schreiben?

oder, als Variation vielleicht näher an Ihrem Fall:

Wir haben diesen Legacy-Code in einem alten, obskuren COBOL-Dialekt geschrieben, für den es keine Spezifikation und / oder keinen Compiler gibt. Wir haben nur das Programm. Unser gesamtes Geschäft ist darauf angewiesen, daher müssen wir 100% ig sicher sein, dass der neue Java-Code in jeder Situation genau das gleiche tut. Das Management wünscht sich ein Programm, das dies tut, alle möglichen Fälle überprüft und schätzt, dass es in 6 bis 8 Wochen durchgeführt werden kann. Warum versuchst du nicht, es zu schreiben?

Es geht nicht darum, ein solches Programm zu schreiben. Oder eine hinreichende Annäherung an die Anforderungen. Der Punkt ist zu erkennen, dass es NICHT auf direktem Weg gemacht werden kann. Verschwenden Sie NICHT unzählige unserer Versuche, herauszufinden, wie es geht (nur um zu erkennen, dass es nicht möglich ist), sondern um es zu erkennen. "Ah! Das ist nicht zu entscheiden! Es ist nicht möglich, es direkt zu tun. Ich muss einen anderen, klügeren Weg finden, um es mit einer hinreichenden Annäherung zu tun."

Sie müssen einen Weg finden, um das Problem auf eine erkennbare und scheinbar einfache Weise darzustellen. Sie würden nicht glauben, wie viele CS-Studenten versuchen werden, ein solches Programm sofort zu schreiben ... bevor sie einen Computability-Kurs belegen :)

Lorenzo Dematté
quelle
Ihr zweites Zitat versucht, das Problem des Anhaltens falsch aufzurufen. Wenn wir jedoch wissen, dass das COBOL-Programm funktioniert und es in einer Testumgebung ausführen kann (vm-clone all PROD, falls erforderlich), ist das Problem des Anhaltens ausgeschlossen, und wir können es versuchen. Wahrscheinlich eher von Hand als per Programm, aber wir können es trotzdem tun. Wir könnten bei Bedarf alle möglichen Eingabeformen in zwei Hälften teilen. Weil das Zielprogramm anhält, hält auch die Baumhalbierung an.
Joshua
2

Angenommen, wir lassen moralische Fragen für den Moment beiseite:

Business A hat mit Ihnen einen Vertrag über die Kommunikation zwischen den Außenstellen A1 und A2 geschlossen, ohne dass außer den befugten Personen in A1 und A2 jemand die Kommunikation verstehen kann.

Business B hat mit Ihnen einen Vertrag abgeschlossen, um die gesamte Kommunikation zwischen A1 und A2 auf intelligente Weise zu überwachen.

Natürlich kann man nicht beides machen.

Aufgrund der Art und Weise, wie die Mathematik funktioniert (die genaue Mathematik wurde 100 Jahre lang kontinuierlich erforscht), kann eine der folgenden Anforderungen nicht erfüllt werden:

(1): Bereitstellung eines Verschlüsselungsalgorithmus, der von einem Angreifer nicht mit einem beliebigen verfügbaren Geldbetrag zerstört werden kann.

(2): Geben Sie einen Algorithmus zum Unterbrechen der Verschlüsselung für einen beliebigen Verschlüsselungsalgorithmus an, der in angemessener Zeit ausgeführt wird.

Joshua
quelle
1
(3):
Wenn
1

Ich habe kürzlich eine Vorlesung über Geschäftsprozessmodell und Notation ( BPMN ) besucht. Dort ist leicht zu erkennen, dass Workflows mit zu vielen Teilungen, Verknüpfungen und Schleifen schnell unpraktisch (wenn auch nicht unbedingt unmöglich , AFAIK) zu verstehen und zu steuern sind (wenn Sie zu viele OR-Teilungen anstelle von XOR-Teilungen verwenden).

Für die Softwareindustrie gilt das Gleiche für ähnliche Probleme der "Mehrfachbedingungsabdeckung" in der Codeabdeckungsanalyse .

Für ein Unternehmen besteht der Weg dahin darin, den Problembereich zu verkleinern und nicht mehr Ressourcen für das komplexe Problem bereitzustellen. Fügen Sie in meinem Beispiel Einschränkungen zum Workflow hinzu (oder vereinfachen Sie den Code bei der Codeabdeckungsanalyse), anstatt hart daran zu arbeiten, alle N möglichen Ablaufverfolgungen und Ergebnisse zu finden, wobei N eine unvorstellbar große Zahl ist.

Abgesehen davon denke ich, dass es viele Probleme in der Netzwerk- / Grafikanalyse gibt , die nicht zu lösen sind (der Versuch, eine Netzwerktopologie durch iteratives Durchlaufen aller Pfade usw. zu bestimmen).

knb
quelle
0

Das klassische Beispiel versucht, HTML mit regulären Ausdrücken zu analysieren . Dies kann mit begrenzten Mengen von HTML funktionieren, aber eine allgemeine Lösung ist unmöglich, da sie unterschiedliche Chomsky-Grammatiken haben (wie der Link klar macht (ish)).

Im Allgemeinen denken manche Leute nicht gerne philosophisch (wie Ihr Kollege), und ich bin mir nicht sicher, ob Sie sich aus einer Denkweise heraus streiten können. Sein erster Punkt ist sicherlich falsch, aber sein zweiter könnte nur eine Möglichkeit sein zu sagen, dass ich mir darüber keine Sorgen machen muss, um Webformulare für den Wareneingang zu codieren. Ich habe ein gewisses Verständnis dafür, aber manchmal bedeutet das Wissen um die Theorie, dass Sie sich nicht dazu verpflichten, den Heiligen Gral in der Arbeitszeit zu finden.

Alistair Mackenzie
quelle
-6

Vielleicht ist die Antwort, dass Ihr Mitarbeiter richtig ist. Vielleicht hast du Turing falsch verstanden, oder wie trifft es hier zu?

Alle Maschinen sind endlich, daher gibt es keine "echten" Turing-Maschinen und keine Programme, die niemals anhalten. Ein triviales Programm, das eine einfache Endlosschleife ausführt, könnte 5 Minuten oder 50 Jahre laufen, aber auf einer endlichen Maschine wird es anhalten. Ein nicht triviales Problem, das nicht anhält, wie z. B. "pi genau berechnen", wird ebenfalls angehalten, da die Berechnung schließlich die Kapazität zum Speichern weiterer Ziffern überschreitet.

Das Turing-Ergebnis garantiert nichts, was auf endlichen Maschinen besonders nützlich ist, sodass Ihre Suche letztendlich erfolglos ist. Konzentrieren Sie sich lieber darauf, wie viel Zeit und wie viel Geld Sie den Mathematikern überlassen.

Sie können denken, dass ein Programm wie { while true: print "running"; print "halted"; }ein Gegenbeispiel ist, aber es ist nicht. Dieses Programm hat Nebenwirkungen, die dazu führen können, dass es angehalten wird oder nicht. Wenn man die Nebenwirkungen ignoriert, ist es möglich, einen formalen Beweis dafür zu erarbeiten, dass dieses Programm nicht anhält. In dieser Frage geht es nur um Programme, die sich dem formellen Beweis der Nichtunterbrechung entziehen, wobei die Frage der Unterbrechung nicht zu entscheiden ist. Dies ist kein solches Programm.

Es kann hilfreich sein, "starkes" Turing von "schwachem" Turing zu unterscheiden. Starke Turing-Maschinen sind eigentlich unendlich und wenn sie nicht anhalten, laufen sie unendlich lange. Wir können diese nicht bauen.

Schwache Turingmaschinen sind zeitlich und räumlich begrenzt, und sie sind die einzige Art, die wir bauen können. Wir sind an Programmen interessiert, bei denen nicht nachgewiesen werden kann, dass sie innerhalb dieser Grenzen anhalten. Turing sagt uns, dass es solche Programme gibt, aber wir können sie nicht identifizieren. Wenn die Grenzen niedrig genug sind, können wir sie identifizieren, indem wir das Programm schreiben und es bis an seine Grenzen laufen lassen.

Das Wesen von Turing ist, dass es keine Abkürzungen gibt. Die einzige Möglichkeit, sicher zu sein, ob ein Problem rechnerisch realisierbar ist, besteht darin, das Programm zu schreiben, es auszuführen und herauszufinden. Mit genügend Zeit und Geld können Sie alle Programme schreiben, sie für immer und im Laufe der Zeit ausführen und diejenigen finden, die Ergebnisse liefern (die Halfter). Die anderen werden noch laufen. Haben Sie genug Zeit und Geld, um das zu tun?

Im Ernst, der Streit geht es um Grenzen. Turing und NP complete teilen uns mit, dass bestimmte Problemklassen nicht von Computern innerhalb eines bestimmten Budgets oder nach einem bestimmten Zeitplan gelöst werden können, unabhängig davon, wie groß dieses Budget oder wie großzügig dieser Zeitplan sein mag. Beispiele für diese Art von Problem gibt es zuhauf: Knacken von kryptografischen Schlüsseln; Optimierung der Routen für Lieferungen an Hunderte von Adressen; Verpackungskästen in Lastwagen; Fehler in großen Programmen finden!

Fragen Sie Ihren Kollegen nach einem Budget und einem Zeitplan und machen Sie das Versprechen, dass Sie ein Problem produzieren können, das innerhalb dieses Budgets oder Zeitplans nicht gelöst werden kann. Dieses Versprechen wird sehr einfach zu halten sein.

david.pfx
quelle
2
Die Essenz des Halteproblems besteht darin, dass es Problemklassen gibt, die niemals berechnet werden können - selbst mit unendlich viel Zeit und Geld. Das ist es, was mein Kollege ablehnt zu akzeptieren.
Jesan Fafon
Dann sind wir nicht einverstanden. Ich habe meine Antwort bearbeitet, aber im Wesentlichen ist die Nachricht dieselbe. Ihre gestellte Frage hat keine Antwort (oder eine, die Ihnen gefällt), aber die ihr zugrunde liegt, ist ein echtes Problem und ein realer Punkt, der angesprochen werden muss. Wenn Sie dieses Argument gewinnen wollen, müssen Sie etwas umdenken, und ich habe versucht, Ihnen dabei zu helfen. [Erinnern Sie mich daran, nicht noch einmal zu versuchen, Fragen wie diese zu beantworten - die negativen Stimmen sind unerwünscht.]
david.pfx
2
@simon: Es besteht die Gefahr, dass ich mich wiederhole. Es gibt keine Programme, die unendlich viel Zeit in Anspruch nehmen, da es keine vollständigen Computer von Turing gibt, sondern nur endliche Annäherungen an diese. Sie können nicht nachweisen, dass ein beliebiges Programm in einer bestimmten Zeitspanne mit einer Methode ausgeführt wird, die schneller ist als die tatsächliche Ausführung des Programms. In der Praxis läuft jeder Satz mit dem Wort "unendlich" Gefahr, keinen Sinn zu ergeben.
david.pfx
3
while True: print "doing stuff"; print "Finished"; Dies ist ein Beispiel für ein Programm, dessen Fertigstellung unendlich viel Zeit in Anspruch nimmt. Es gibt unendlich viele andere Programme, die ebenfalls unendlich viel Zeit in Anspruch nehmen. Wir erstellen regelmäßig Programme, deren absichtliche Fertigstellung unendlich viel Zeit in Anspruch nimmt. Sie werden als "Langzeitprozesse" bezeichnet. Die meisten dynamischen Websites sind Beispiele dafür.
Singletoned
2
Der Punkt ist sicherlich, dass es eine Reihe von Computerprogrammen gibt, die praktisch unendlich sind. Sie werden niemals aus eigener Kraft anhalten (wir werden die Pause drücken, die Stromversorgung unterbrechen usw.), wenn wir sie in eine Turing-Maschine programmieren würden laufen ohne anzuhalten. Die Essenz des Halteproblems ist, dass es praktisch oder theoretisch keine Möglichkeit gibt, überhaupt nicht haltende Programme algorithmisch zu bestimmen.
Alistair Mackenzie