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

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?

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.

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 :)

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.

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).

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.

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.