Problem transkomputacyjny

W teorii złożoności obliczeniowej problem transkomputacyjny to problem , który wymaga przetworzenia więcej niż 10 93 bitów informacji. Każda liczba większa niż 10 93 nazywana jest liczbą transobliczeniową . Liczba 10 93 , zwana granicą Bremermanna , jest według Hansa-Joachima Bremermanna całkowitą liczbą bitów przetwarzanych przez hipotetyczny komputer wielkości Ziemi w okresie równym szacunkowemu wiekowi Ziemi. Termin transkomputacyjny został ukuty przez Bremermanna.

Przykłady

Testowanie układów scalonych

Dokładne przetestowanie wszystkich kombinacji układu scalonego z 309 wejściami binarnymi i 1 wyjściem wymaga przetestowania łącznie 2 309 kombinacji wejść. Ponieważ liczba 2 309 jest liczbą transobliczeniową (czyli liczbą większą niż 10 93 ), problem testowania takiego układu układów scalonych jest problemem transobliczeniowym. Oznacza to, że nie ma możliwości zweryfikowania poprawności obwodu dla wszystkich kombinacji wejść za pomocą samej brutalnej siły .

Rozpoznawanie wzorców

Rozważmy tablicę q × q typu szachownicy , której każdy kwadrat może mieć jeden z k kolorów . W sumie istnieje k n wzorców kolorów , gdzie n = q 2 . Problem określenia najlepszej klasyfikacji wzorów według wybranego kryterium można rozwiązać poprzez przeszukanie wszystkich możliwych wzorów kolorystycznych. W przypadku dwóch kolorów takie wyszukiwanie staje się transkomputacyjne, gdy tablica ma rozmiar 18 × 18 lub większy. W przypadku tablicy 10 × 10 problem staje się transkomputacyjny, gdy jest 9 lub więcej kolorów.

Ma to pewne znaczenie w badaniach fizjologicznych siatkówki . Siatkówka zawiera około miliona komórek światłoczułych . Nawet gdyby istniały tylko dwa możliwe stany dla każdej komórki (powiedzmy stan aktywny i stan nieaktywny), przetwarzanie siatkówki jako całości wymaga przetworzenia ponad 10 300 000 bitów informacji. To daleko poza limitem Bremermanna .

Ogólne problemy systemowe

Układ n zmiennych, z których każda może przyjmować k różnych stanów, może mieć k n możliwych stanów systemu. Aby przeanalizować taki system, należy przetworzyć minimum k n bitów informacji. Problem staje się transobliczeniowy, gdy k n > 10 93 . Dzieje się tak dla następujących wartości k i n :

k 2 3 4 5 6 7 8 9 10
N 308 194 154 133 119 110 102 97 93

Implikacje

Istnienie problemów transkomputacyjnych w świecie rzeczywistym implikuje ograniczenia komputerów jako narzędzi do przetwarzania danych. Ten punkt najlepiej podsumowują własnymi słowami Bremermanna:

„Doświadczenia różnych grup zajmujących się rozwiązywaniem problemów, dowodzeniem twierdzeń i rozpoznawaniem wzorców wydają się wskazywać ten sam kierunek: te problemy są trudne. Wydaje się, że nie ma królewskiej drogi ani prostej metody, która za jednym zamachem rozwiąże wszystkie nasze problemy. Moje omówienie ostatecznych ograniczeń szybkości i ilości przetwarzania danych można podsumować w następujący sposób: Problemów obejmujących ogromną liczbę możliwości nie rozwiąże sama ilość przetwarzania danych. Musimy szukać jakości, udoskonaleń, sztuczek , dla każdej pomysłowości, jaką możemy wymyślić. Komputery szybsze niż dzisiejsze będą bardzo pomocne. Będziemy ich potrzebować. Jednak gdy zajmujemy się problemami w zasadzie, dzisiejsze komputery są tak szybkie, jak nigdy dotąd .
Można się spodziewać, że technologia przetwarzania danych będzie postępowała krok po kroku – tak jak zwykła technologia. Istnieje nieograniczone wyzwanie dla pomysłowości zastosowanej do konkretnych problemów. Istnieje również niekończąca się potrzeba ogólnych pojęć i teorii, aby uporządkować niezliczone szczegóły”.

W fikcji

W książce Douglasa Adamsa The Hitchhiker's Guide to the Galaxy Ziemia jest superkomputerem zaprojektowanym do obliczania pytania znanego jako „Ostateczne pytanie o życie, wszechświat i wszystko” (wiadomo, że odpowiedź na to pytanie to 42).

Zobacz też

Pobrane z „ https://en.wikipedia.org/w/index.php?title=Transcomputational_problem&oldid=1058742700 ”