Czego nie da się obecnie zaprogramować

Z Wikipedii

Od początku istnienia informatyki wiązano z komputerami bardzo duże nadzieje, niektóre z nich wydają się teraz leżeć na pograniczu fantastyki. Ludzie wyobrażali sobie, że komputer będzie mógł robić wszystko to, co robi człowiek (łącznie z wizjami zbuntowanych komputerów przejmujących władzę nad światem). W rzeczywistości tak się nie stało.

Klasyfikacja zagadnień, których informatyka nie potrafi rozwiązać powinna rozróżniać nastepujące nurty, wynikające z analizy złożoności obliczeniowej problemów (w kolejności od najłatwiej przezwyciężalnych do niemożliwych do rozwiązania):

• Problemu nie da się rozwiązać, gdyż konieczna jest moc obliczeniowa niedostępna współcześnie lub być może nigdy (gra w go, dokładna symulacja niektórych złożonych procesów fizycznych).
• Problemu nie da się rozwiązać, gdyż nie potrafimy określić jak mógłby wyglądać algorytm, który go rozwiązuje; być może algorytm taki nie istnieje, jednak tego nie wiemy (analiza języka naturalnego, rozumienie rzeczywistości tj. związków między informacjami) a nawet nie bardzo rozumiemy o czym mówimy (np. sztuczna inteligencja). Z powodów braku dobrej definicji nie potrafimy efektywnie ocenić, do jakiej klasy należą te problemy: niektóre mogą okazać się proste (np. rozróżnianie języka, do niedawna uważane za trudne) dla innych nie potrafimy poprawnie postawić zagadnienia.
• Problemu nie da się rozwiązać, gdyż należy on do klasy "trudnych problemów" (NP-zupełnych). Są to problemy, dla których jakiś algorytm jest zwykle bardzo łatwo napisać, natomiast jego czas działania rośnie wykładniczo lub nadwykładniczo (czyli jak silnia) z ilością danych wejściowych. Na ogół nie wiadomo czy istnieją lepsze (szybsze niż wykładnicze) algorytmy rozwiązujące te problemy. Przykładem takiego problemu jest problem komiwojażera. W tym wypadku dla dowolnej wydajności obliczeniowej można zadać takie dane wejściowe (np. ilość miast w problemie komiwojażera), że przekroczymy granicę obliczalności i nie znamy algorytmu który rozwiązywałby problem komiwojażera w czasie wielomianowym względem rozmiaru danych wejściowych. Co jakiś czas zdarza się, że ktoś znajduje efektywny algorytm rozwiązujący problem wcześniej uważany za problem klasy NP. Jednak nadal nie wiadomo czy da się w ten sposób rozwiązać wszystkie problemy NP.
• Natura problemu jest tak złożona, że niemożliwe staje się rozwiązanie go z powodu ograniczeń wynikających z paradygmatu obliczeniowego: np. w wypadku długoterminowych prognoz pogody dane początkowe (temperatury, ciśnienia) znamy ze skończoną dokładnością, co sprawia, że dla pewnego horyzontu czasowego niepewność symulacji przekracza rozsądne granice. Własność taką nazywamy niestabilnością rozwiązań, jest ona cechą zjawiska i wynika z samej jego natury. Inne przykłady tego typu zachowań podaje teoria chaosu.
• Problemu nie da się rozwiązać, bo wiemy że nie istnieje algorytm rozwiązujący ten problem (problem stopu, normalizacja wyrażeń w gramatykach formalnych itp. zwykle związane z formalnym problemem matematycznym zagadnienia).

[edytuj] Gry

Grą, której poświęcono najwięcej wysiłku, były szachy. Wysiłek ten zakończył się sukcesem, czyli powstaniem programu (działającego na superkomputerze Deep Blue) pokonującego nawet mistrza świata Garriego Kasparowa w maju 1997. Nawet niezbyt ambitny program szachowy bez problemu radzi sobie z przeciętnym graczem.

Programy grające w niektóre inne gry jak na razie nie odniosły tak spektakularnych sukcesów. Największą porażką komputerów jest całkowita nieumiejętność gry w go – jedną z najpopularniejszych gier strategicznych na świecie. Najlepsze programy grają na poziomie kilku kyuu, i są bez problemu pokonywane przez nawet średnich graczy.

Inną grą, w której programy komputerowe nie radzą sobie najlepiej jest brydż.

[edytuj] Przetwarzanie języków naturalnych

Komputery nie najlepiej sobie radzą z przetwarzaniem języków naturalnych. Zachodzi tu pewien paradoks – informatyka dokonała przewrotu w lingwistyce dostarczając zaawansowanych narzędzi do analizy języka naturalnego (począwszy od gramatyk generatywno-transformacyjnych), jednak komputery zupełnie nie potrafią sobie z tym problemem poradzić.

Żaden program nie potrafi zadowalająco tłumaczyć tekstów między językami naturalnymi, jednak potrafią one dać zadowalające "szkicowe tłumaczenie" oraz wspierać tłumacza (np. wyszukując rzadko używane słowa i zwroty). Trudności są dwie – pierwsza to kontekst i umiejętność wykorzystania wiedzy w danej dziedzinie, drugą jest to, że "dobre tłumaczenie" jest pojęciem dotyczącym bardziej estetyki niż informatyki. Tłumaczenie całkowicie poprawne może z tych czy innych względów nie podobać się ludziom, co jeszcze bardziej utrudnia niełatwą już pracę komputera.

Drugim problemem jest program naśladujący ludzką rozmowę. Najlepsze programy tego typu potrafią dość długo (czas rzędu do kilkunastu minut) utrzymać rozmówcę w przekonaniu, że rozmawia z człowiekiem, szczególnie jeśli rozmowa jest "o niczym" i toczy się takim kanałem komunikacji, jakim jest na przykład IRC. Obecnie synteza ludzkiego głosu nie stwarza takich możliwości, dlatego dotyczy to tylko tekstu pisanego. Jak na razie najlepsze tego typu programy są oparte na prostym dopasowywaniu wzorca, bibliotece odpowiedzi i dużym arsenałem sztuczek – jeden ";-)" w odpowiednim miejscu potrafi więcej zdziałać niż zdania wielokrotnie złożone. Metodyka ta jest całkowitym zaprzeczeniem metod "sztucznej inteligencji" i niewielkie są szanse, że takie programy będą potrafiły coś więcej niż "gadać o niczym".

Ciekawym problemem uważanym dawniej za złożony, a który okazał się zdumiewająco prosty, jest rozróżnianie języka (np. automatyczne rozpoznanie bez zrozumienia treści, że tekst jest francuski lub hebrajski, albo chociaż, że dwa teksty są w różnych językach). Okazało się, że stosując algorytm kompresji deflate (stosowany w programie gzip) rozróżnia się dzięki różnemu stopniowi kompresji różne języki na poziomie 98% trafności predykcji.

Zobacz też: test Turinga.

Link zewnętrzny: rozpoznawanie języka tekstu pisanego firmy Xerox (online).

[edytuj] Giełda

Jak na razie nie napisano programu, który potrafiłby skutecznie generować zysk, inwestując na giełdzie. Problemem jest nie tyle masa informacji, którą taki program musiałby "przetworzyć" i sposób wprowadzania tych informacji do komputera, co jest zadaniem generalnie rzecz biorąc łatwym, co kompletny brak modelu teoretycznego pozwalającego określić jakie dane należy wprowadzać. Komputer bowiem wbrew intuicji z liceum, nie myśli i nie potrafi oceniać ważności informacji, zaś statystyczna zależność pomiędzy dwiema seriami doświadczalnymi liczb (powiedzmy WIG20 i kurs dolar-złoty) nie oznacza istnienia jakiejkolwiek zależności deterministycznej pomiędzy tymi dwiema wielkościami, a jedynie możliwość jej istnienia. Znane są przypadki, że wielkości zależne od siebie deterministycznie nie wykazują jakiejkolwiek zależności statystycznej (chaos) oraz kiedy ja wykazują (ciśnienie- temperatura itp.). Z drugiej jednak strony nie ma na świecie maklera, który potrafiłby inwestować bez użycia komputera. Wprowadzenie programu, który potrafiłby dokonać analizy lepiej niż inne programy mogłoby przynieść korzyści dla osób, które jako pierwsze będą z niego korzystały, po upowszechnieniu się programu wszyscy będą mieli znowu takie same szanse na osiągnięcie zysku.