Kardynalność zbioru algorytmów

Ktoś w dyskusji przywołał, że (uważa) może istnieć co najmniej ciągła liczba strategii podejścia do określonego problemu. Specyficznym problemem były strategie handlowe (nie algorytmy, ale strategie), ale myślę, że to nie ma znaczenia dla mojego pytania.

To sprawiło, że pomyślałem o liczności zbioru algorytmów. Trochę szukałem, ale nic nie wymyśliłem. Myślałem, że ponieważ maszyny Turinga działają ze skończonym zestawem alfabetów, a taśma musi być indeksowalna, a zatem policzalna, niemożliwe jest posiadanie niezliczonej liczby algorytmów. Moja teoria zbiorów jest wprawdzie zardzewiała, więc nie jestem wcale pewien, czy moje rozumowanie jest prawidłowe i prawdopodobnie nie byłbym w stanie tego udowodnić, ale to ciekawa myśl.

Jaka jest liczność zbioru algorytmów?

Algorytm jest nieformalnie opisany jako skończona sekwencja pisemnych instrukcji wykonania określonego zadania. Mówiąc bardziej formalnie, są one identyfikowane jako maszyny Turinga, choć równie dobrze można je opisać jako programy komputerowe.

Dokładny formalizm, którego używasz, nie ma większego znaczenia, ale podstawową kwestią jest to, że każdy algorytm można zapisać jako skończoną sekwencję znaków, przy czym znaki są wybierane z pewnego zbioru skończonego, np. Liter rzymskich, ASCII lub zer i jedynek. Dla uproszczenia załóżmy, że zera i jedynki. Każda sekwencja zer i jedynek jest po prostu liczbą naturalną zapisaną dwójkowo. Oznacza to, że istnieje co najwyżej policzalna nieskończoność algorytmów, ponieważ każdy algorytm może być reprezentowany jako liczba naturalna.

Aby uzyskać pełne uznanie, należy się martwić, że niektóre liczby naturalne mogą nie kodować prawidłowych programów, więc algorytmów może być mniej niż liczb naturalnych. (Dla kredytu bonusowego, możesz też się zastanawiać, czy to możliwe, że dwie różne liczby naturalne reprezentują ten sam algorytm). Jednak print 1, print 2, print 3i tak dalej są wszystkie algorytmy i wszystko inne, tak istnieją co najmniej przeliczalnie nieskończenie wiele algorytmów.

Dochodzimy zatem do wniosku, że zestaw algorytmów jest w nieskończoność nieskończony.

Zestaw algorytmów jest nieskończenie nieskończony. Dzieje się tak, ponieważ każdy algorytm ma skończony opis, na przykład maszynę Turinga.

Fakt, że algorytm ma skończony opis, pozwala nam wprowadzić jeden algorytm do drugiego, i to jest podstawa teorii obliczalności. Pozwala nam na przykład sformułować problem zatrzymania.

przynajmniej ciągła liczba strategii podejścia do określonego problemu

„Continuum” prawdopodobnie ma oznaczać liczby rzeczywiste… użycie „co najmniej” razem z tym słowem jest absurdalnie przesadzone. Mówiąc trochę głupio: niezliczona nieskończoność jest dość duża, ale niezliczona nieskończoność jest ... większa niż duża. O wiele bardziej. Niezgłębione.

Wyrzućmy to przez okno. Aby zobaczyć, z jaką nieskończonością mamy do czynienia, jest śmiertelnie prosta (i intuicyjna, nawet jeśli twój przyjaciel nigdy nie słyszał o teoretycznych informatykach):

• Dowolny algorytm może być zaimplementowany w dowolnym języku kompletnym; wybierz swoją ulubioną truciznę języków rzeczywistych (Java, C, ...), aby nieco to zdezkrypować. Wszystko to jest równoważne z teoretycznym zestawem algorytmów, które każdy mógłby kiedykolwiek wymyślić. Zauważ, że każdy algorytm sam w sobie jest skończony, tzn. Nie ma algorytmów, których zapisanie wymagałoby nieskończenie wielu symboli.
• Nie myśl o skomplikowanych maszynach Turinga. Twój wybrany język używa prostych plików do przechowywania kodu źródłowego. Każdy plik jest zbiorem małych liczb (aka, bajtów). Ważne jest to, że te liczby są zdecydowanie liczbami całkowitymi, a nie ciągłymi. (Jeśli jesteś purystą i chcesz pozostać w reżimie teoretycznym, zamień słowo „bajt” na „symbol”, nic to nie zmieni.) Jeśli boisz się dużych programów, które są rozproszone w wielu plikach (i bibliotekach) i inne rzeczy), a następnie spakuj je do jednego skompresowanego archiwum (tj. jednego pliku).
• Teraz możesz przypisać pojedynczą liczbę całkowitą do każdego pliku tam, biotycznie. Po prostu zapisujemy cały bałagan bitów / bajtów pliku, jeden po drugim, i otrzymujemy bardzo dużą liczbę wyrażoną w formacie binarnym. W odległej przeszłości ludzie faktycznie to robili: drukowali skompilowane programy binarne jako długie listy liczb szesnastkowych w czasopismach; wpisujesz je, ale nigdy nie widzisz ich jako nic innego niż liczby (często pogrupowane w zestawy 8- lub 16-cyfrowe, aby ułatwić pisanie).
• Tak więc: każdy program może być reprezentowany przez liczbę całkowitą, choć dowolną dużą. Odwrotna metoda również działa - każda liczba całkowita może być natychmiast i trywialnie przeniesiona do pliku i wyrzucona do kompilatora (oczywiście tylko niewielka część z nich będzie poprawnymi programami, ale teraz nie ma to dla nas znaczenia).
• Ostatecznie programy, a tym samym algorytmy, są podzbiorem liczb całkowitych; stąd tylko licznie wiele może istnieć.
• NB, fakt, że istnieje wiele różnych implementacji jednego algorytmu, jest na naszą korzyść, to znaczy wiele z tych liczb całkowitych zagęszcza się w (różnych reprezentacjach) tego samego algorytmu. Więc jeśli policzalna nieskończoność nie była już najmniejszą nieskończonością, musielibyśmy się martwić, że liczba algorytmów będzie jeszcze mniejsza, ale na pewno nie większa (tj. Niepoliczalna).

Specyficznym problemem były strategie handlowe (nie algorytmy, ale strategie)

Nie wiem, co oznacza twój przyjaciel z „strategią”; Zakładam, że ma na myśli coś, co przypomina algorytm, ale nie jest wystarczająco sformułowane wystarczająco szczegółowo, aby włamać się do komputera? Czy które w jakiś sposób zależy od ludzkiej „intuicji” podczas egzekucji? Jeśli tak, to są to tylko nieistotne szczegóły. Ludzkość nie znalazła jeszcze żadnego opisu procesów, który byłby silniejszy lub większy niż „algorytmy” w takim sensie, jakiego używamy w CS.

Patrz Gödel Numbering . Podstawowym faktem w informatyce jest to, że algorytmy są policzalne, podobnie jak zestawy rekurencyjnie policzalne.

Algorytmy są policzalne, łatwo jest wykazać, że nie istnieje algorytm weryfikujący każdy zestaw w systemie formalnym (przypisując wartość prawdy do problemu). Byłoby to równoznaczne z przypisaniem algorytmu do każdej funkcji mapującej zestaw problemów na wartości boolowskie. Zbiór tych funkcji jest jednak niepoliczalny (trywialnie tej samej liczności co zbiór mocy zestawu problemów, a zatem niepoliczalny).

Mam nadzieję, że daje to pewną intuicję, dlaczego algorytmy muszą być „mniej wydajne” niż jakakolwiek funkcja, a więc policzalne (zignorujmy tutaj hipotezę kontinuum).

Jeśli nie zaczniesz od wymogu, że strategia musi być możliwa do implementacji za pomocą algorytmu i zignoruje rzeczywiste efekty dyskretyzacji, możesz na przykład zaakceptować następujące parametry jako sparametryzowaną strategię handlową:

$a$$b$$a$$b$

$a$$b$

Jeśli wyobrażamy sobie algorytmy jako programy komputerowe zapisane w formacie binarnym *, wówczas liczba algorytmów jest liczbą (liczb całkowitych) liczb binarnych. Zatem liczność algorytmów jest licznością liczb całkowitych.

* Dowód, że maszyny Turinga mogą uruchamiać wszystkie algorytmy i że komputery mogą uruchamiać dowolne maszyny Turinga, uczyniłoby tę odpowiedź niepotrzebnie długą. Ten pierwszy może zależeć od definicji algorytmu, ale nie sądzę, że używasz niezliczonych strategii handlowych.

Inne odpowiedzi już wyjaśniły, że w standardowym modelu obliczeń (maszyny Turinga, rachunek lambda itp.) Zbiór algorytmów jest w nieskończoność nieskończony.

Istnieją jednak inne teoretyczne modele obliczeń, w których zbiór algorytmów jest niepoliczalnie nieskończony. Na przykład maszyny Blum – Shub – Smale mają niepoliczalnie nieskończony zestaw instrukcji ¹ , więc ich zestaw algorytmów jest również nieskończenie nieskończony.

ponieważ maszyny Turinga działają ze skończonym zestawem alfabetu, a taśma musi być indeksowalna, a zatem policzalna

Biorąc pod uwagę konkretny rozmiar, istnieje ostatecznie wiele maszyn Turinga i istnieje niezliczona ilość rozmiarów. Zliczalny zestaw liczb, o ile są skończone, można policzyć. Rozmiar alfabetu jest czynnikiem wpływającym na liczbę maszyn Turinga, ale rozmiar taśmy nie. Gdyby pozwolono, aby alfabet miał licznie wiele znaków, wówczas istniałoby niepoliczalnie wiele maszyn (każda liczba rzeczywista mogłaby być zakodowana jako sekwencja symboli).

Jeśli „algorytm” oznacza jedynie zgodność między danymi wejściowymi i wyjściowymi, a nie maszynę Turinga lub w inny sposób coś, co jest normalnym sensem „obliczeń”, to oczywiście, jeśli istnieje niezliczona ilość różnych danych wejściowych, wówczas istnieje niezliczona ilość algorytmów: dla dla każdej liczby rzeczywistej moglibyśmy zdefiniować „algorytm”, który przyjmuje liczbę naturalną jako dane wejściowe i generuje to miejsce po przecinku. Na przykład, wpisując „3” do$\sqrt{.5}$algorytm dałby wynik „7”. (Należy pamiętać, że chociaż możliwe jest zaprojektowanie maszyny Turinga, która daje n-tą cyfrę$\sqrt{.5}$nie można tego zrobić dla wszystkich liczb rzeczywistych; tylko policzalnie wiele liczb rzeczywistych jest obliczalnych).