Jaki jest przykład problemu biznesowego niemożliwego do obliczenia?

Mam współpracownika, który odmawia zaakceptowania rzeczywistości, w której maszyny Turinga (a także maszyny von Neumana) nie są w stanie rozwiązać własnego problemu zatrzymania, stwierdzając:

Możesz zrobić wszystko, mając wystarczająco dużo czasu i pieniędzy.

Nie lubi też problemów teoretycznych, argumentując, że:

W naszej dziedzinie nigdy nie napotkamy na te pytania. Jesteśmy twórcami aplikacji, a nie naukowcami teoretycznymi.

Czy istnieje dobry przykład problemu biznesowego, który jest obliczeniowo niemożliwy, którego mógłbym użyć, aby przekonać go o tym?

Nie technicznie niemożliwe, ale ...

Planowanie zasobów w celu znalezienia idealnego harmonogramu maksymalizującego wykorzystanie przedziałów czasowych. Kiedyś, podczas moich wcześniejszych obliczeń, miałem projekt, który wymagał tego. Pracowałem nad tym przez jakiś czas, zanim zdałem sobie sprawę, że było to trudne dla NP.

Inne przykłady problemów, które nie są technicznie niemożliwe, ale są technicznie trudne, można znaleźć tutaj .

Większość trudnych problemów obliczeniowych w informatyce biznesowej nie jest niemożliwa, tylko niepraktyczna. Twój przyjaciel ma rację; możesz rozwiązać większość z nich, jeśli rzucisz na nie wystarczającą ilością pieniędzy. Ale argument jest podstępny; sednem prowadzenia firmy jest zarabianie pieniędzy, a nie ich tracenie.

W codziennej praktyce mówimy o kompletności Turinga w sposób niejasny, nie po to, by zademonstrować jakąś matematyczną zasadę, ale aby zilustrować (na przykład) nieadekwatność HTML i CSS jako kompletnego narzędzia do tworzenia programów z pełną funkcjonalnością.

Podobnie problem zatrzymania jest ważny dla teoretyków, ale nie ma większego znaczenia dla większości firm.

Inni skomentowali to, ale spróbuję napisać odpowiedź, podając mój punkt widzenia.

Podoba mi się odpowiedź Roberta Harveya i komentarze do jego odpowiedzi, i chciałbym rozwinąć je.

Myślę, że musisz przedstawić te nierozstrzygalne problemy (takie jak zakończenie) w przyziemny sposób: na przykład narzędzie IDE, które „sprawdza, czy ta funkcja zawsze zwraca wartość”.

Podczas nauczania moim ulubionym przykładem było refaktoryzacja ( równoważność funkcji, kolejny nierozstrzygalny problem ). Zapytałam:

Jak sprawdzisz, czy funkcja / program robi to samo po ładnym refaktoryzacji? Oczywiście, mamy na to testy jednostkowe, ale nie obejmują one wszystkich przypadków. I nudzą się pisać ... Ale jesteśmy programistami! Powinniśmy napisać program, który sprawdza, czy te dwie funkcje dają zawsze ten sam wynik! Dlaczego nie spróbujesz tego napisać?

lub, jako wariant może być bliżej twojej sprawy:

Mamy ten starszy kod napisany w starożytnym, niejasnym dialekcie COBOL, dla którego nie ma specyfikacji ani kompilatora. Mamy tylko program. Cała nasza działalność na tym polega, dlatego musimy być w 100% pewni, że nowy kod Java robi dokładnie to samo w każdej sytuacji. Kierownictwo chce programu, który to robi, sprawdzając wszystkie możliwe przypadki i szacuje, że można to zrobić w ciągu 6 do 8 tygodni. Dlaczego nie spróbujesz tego napisać?

Nie chodzi o to, żeby napisać taki program. Lub wystarczająco dobre przybliżenie wymagań. Chodzi o to, aby uświadomić sobie, że NIE można tego zrobić bezpośrednio, NIE marnuj niezliczonej ilości naszych, próbując wymyślić, jak to zrobić (tylko aby uświadomić sobie, że nie jest to możliwe), ale rozpoznaj to. „Ach! To nierozstrzygalne! Nie można tego zrobić bezpośrednio. Muszę wymyślić inny, bardziej sprytny sposób, z wystarczającym przybliżeniem”.

Musisz wymyślić sposób przedstawienia problemu w rozpoznawalny i pozornie prosty sposób. Nie uwierzyłbyś, ilu studentów CS spróbuje napisać taki program od razu ... przed przystąpieniem do klasy obliczeniowej :)

Zakładając, że na razie możemy odłożyć na bok pytania moralne:

Firma A zawarła z tobą umowę na sposób komunikacji między biurami satelitarnymi A1 i A2, przy czym nikt poza osobami upoważnionymi w A1 i A2 nie jest w stanie zrozumieć komunikacji.

Firma B zawarła z tobą umowę na sposób inteligentnego podsłuchiwania wszelkiej komunikacji między A1 i A2.

Oczywiście nie możesz zrobić obu.

Ze względu na sposób działania matematyki (dokładna matematyka jest przedmiotem ciągłych badań od 100 lat) nie można spełnić jednego z następujących wymagań:

(1): Podaj algorytm szyfrowania, którego atakujący nie może złamać, mając do dyspozycji dowolną ilość pieniędzy.

(2): Zapewnij algorytm łamania szyfru dla dowolnego algorytmu szyfrowania, który działa w rozsądnym czasie.

Ostatnio wziąłem udział w zajęciach na temat modelu i notacji biznesowej ( BPMN ). Łatwo zauważyć, że przepływy pracy z wieloma zbyt podziałami, złączeniami i pętlami stają się szybko niepraktyczne (choć niekoniecznie niemożliwe , AFAIK) do zrozumienia i kontrolowania (gdy używasz zbyt wielu podziałów OR zamiast podziałów XOR).

W branży oprogramowania myślę, że to samo dotyczy podobnych problemów związanych z „pokryciem wielu warunków” w analizie pokrycia kodu .

W przypadku firmy najlepszym sposobem jest zmniejszenie przestrzeni problemowej i nie rzucanie więcej zasobów na skomplikowany problem. W moim przykładzie dodaj ograniczenia do przepływu pracy (lub w analizie pokrycia kodu uprość kod), zamiast ciężko pracować nad znalezieniem wszystkich, powiedzmy, N możliwych śladów i wyników, w których N jest niewyobrażalnie dużą liczbą.

Poza tym myślę, że istnieje wiele problemów w analizie sieci / wykresów , których nie można rozwiązać (próba ustalenia topologii sieci poprzez iteracyjne kroczenie wszystkimi ścieżkami itp.).

Klasycznym przykładem jest próba parsowania HTML z wyrażeniami regularnymi . Może to działać z ograniczonymi zestawami HTML, ale ogólne rozwiązanie jest niemożliwe ze względu na fakt, że mają one inną gramatykę Chomsky'ego (jak wyjaśnia link (ish)).

Mówiąc bardziej ogólnie, niektórzy ludzie nie lubią myśleć filozoficznie (jak twój współpracownik) i nie jestem pewien, czy potrafisz wyprowadzić się z umysłu. Jego pierwszy punkt jest z pewnością błędny, ale jego drugi może być po prostu sposobem na powiedzenie, że nie muszę się tym martwić, aby kodować formularze internetowe do odbioru towarów. Mam z tym trochę sympatii, ale czasami znajomość teorii oznacza, że ​​nie angażujesz się w szukanie Świętego Graala w czasie pracy.

Być może odpowiedzią jest, że twój współpracownik ma rację. Być może źle zrozumiałeś Turinga lub jak to tutaj ma zastosowanie?

Wszystkie maszyny są skończone, dlatego nie ma „prawdziwych” maszyn Turinga i programów, które nigdy się nie zatrzymają. Trywialny program, który wykonuje prostą nieskończoną pętlę, może działać 5 minut lub 50 lat, ale na skończonej maszynie się zatrzyma. Zatrzymany zostanie również nietrywialny problem nie zatrzymujący się, taki jak „dokładnie oblicz liczbę pi”, ponieważ ostatecznie obliczenia przekroczą pojemność do przechowywania kolejnych cyfr.

Wynik Turinga nie gwarantuje niczego szczególnie przydatnego na skończonych maszynach, więc twoje zadanie jest ostatecznie bezowocne. Lepiej skoncentruj się na tym, ile czasu i pieniędzy, i pozostaw matematykom nieskończoność.

Może ci się wydawać, że taki program { while true: print "running"; print "halted"; }jest kontrapunktem, ale nim nie jest. Ten program ma skutki uboczne, które mogą powodować zatrzymanie. Ignorując skutki uboczne, można opracować formalny dowód, że ten program się nie zatrzyma. W tym pytaniu zajmujemy się tylko programami, które unikają formalnego dowodu braku zatrzymania, gdy kwestia zatrzymania jest nierozstrzygalna. To nie jest taki program.

Pomoże to odróżnić „silne” Turinga od „słabego” Turinga. Silne maszyny Turinga są w rzeczywistości nieskończone i jeśli się nie zatrzymają, będą działać przez nieskończony czas. Nie możemy ich zbudować.

Słabe maszyny Turinga mają ograniczone limity czasu i przestrzeni i są jedynym rodzajem, jaki możemy zbudować. Interesują nas programy, których zatrzymania w tych granicach nie można udowodnić. Turing mówi nam, że istnieją takie programy, ale nie możemy ich zidentyfikować. Jeśli limity są wystarczająco niskie, możemy je zidentyfikować, pisząc program i uruchamiając go do granic możliwości.

Istotą Turinga jest to, że nie ma skrótów. Jedynym sposobem, aby upewnić się, czy problem jest wykonalny obliczeniowo, jest napisanie programu, uruchomienie go i sprawdzenie. Mając wystarczająco dużo czasu i pieniędzy, możesz napisać wszystkie programy, uruchamiać je na zawsze i z czasem oraz znaleźć te, które przynoszą rezultaty (kantary). Pozostałe nadal będą działać. Czy Twój współpracownik ma wystarczająco dużo czasu i pieniędzy, aby to zrobić?

Poważnie jednak spór dotyczy granic. Turing i NP complete mówią nam, że pewne klasy problemów nie mogą być rozwiązane przez komputery w ramach danego budżetu lub harmonogramu, bez względu na to, jak duży budżet i jak hojny może być ten harmonogram. Przykładów tego rodzaju problemów jest wiele: łamanie kluczy kryptograficznych; optymalizacja tras dostaw do setek adresów; pakowanie pudeł w ciężarówki; znajdowanie błędów w dużych programach!

Poproś więc współpracownika o budżet i harmonogram i złóż obietnicę, że możesz stworzyć problem, którego nie da się rozwiązać w ramach tego budżetu lub harmonogramu. Ta obietnica będzie bardzo łatwa do dotrzymania.