Aby odpowiedzieć „jakie problemy można rozwiązać za pomocą komputera”, opracowaliśmy teorię obliczalności. Czy w przypadku problemów, które można obliczać, istnieje teoria, która pozwala odpowiedzieć na pytanie „czy program otrzymuję najprostszy”?
Nie sądzę, aby złożoność obliczeniowa odpowiadała na pytanie. Myślę, że bierze pod uwagę, jak długo potrzebujemy (choć mierzone abstrakcyjnie).
Nie jestem pewien, czy algorytmiczna teoria informacji odpowiada na pytanie. Wydaje się, że teoria mówi o rozmiarze, w którym równoważność minimalnego i najprostszego nie jest dla mnie oczywista (cóż, przynajmniej mnie różnią się).
Myślę, że teoria powinna przynajmniej definiować relację „prosta” lub „prostsza niż”.
Jestem teraz przekonany, że powinienem przyjrzeć się złożoności Kołmogorowa. Chciałbym jednak wyjaśnić, co miałem na myśli, kiedy zadawałem to pytanie.
Kiedy ulepszam program, staram się redukować niepotrzebne połączenia między różnymi częściami programu (być może ponowne dzielenie części, aby było mniej lub słabiej). Ponieważ połączenia są zmniejszone, program wydaje się „prostszy”. Stąd wybór słowa „prosty”, kiedy formułuję pytanie. Jest bardzo prawdopodobne, że rozmiar programu również się zmniejsza, ale jest to dobry efekt uboczny, a nie główny cel. Oczywiście proces poprawy nie może trwać wiecznie. Jest kwestia, którą powinienem zatrzymać. Jeśli tylko rozważając „strukturę” (przepraszam za inną niezdefiniowaną koncepcję) lub „relację”, czy mogę się przekonać, że nic więcej nie można zrobić?
Oto lepszy opis mojego pojęcia złożoności.
Olaf Sporns (2007) Złożoność . Scholarpedia , 2 (10): 1623