Dlaczego możemy założyć, że algorytm może być reprezentowany jako ciąg bitowy?

Zaczynam czytać książkę o złożoności obliczeniowej i maszynach Turinga. Oto cytat:

Algorytm (np. Maszyna) może być reprezentowany jako ciąg bitów, gdy zdecydujemy się na pewne kodowanie kanoniczne.

To twierdzenie zostało przedstawione jako prosty fakt, ale nie rozumiem tego.

Na przykład, jeśli mam algorytm, który przyjmuje jako dane wejściowe i oblicza ( x + 1 ) 2 lub:$x$$(x+1)^2$

int function (int x){
   x = x + 1; 
   return x**2; 
}

Jak można to przedstawić jako ciąg znaków za pomocą alfabetu ?$\{0, 1\}^*$

Najbardziej naiwną i prostą odpowiedzią na twoje pytanie jest to, że podany kod (i skompilowany kod maszynowy) są w rzeczywistości reprezentowane jako ciągi składniowe {0,1} *. Ponadto, ponieważ mówimy o maszynach Turinga, uruchamiane przez nich programy są liniową listą operacji / instrukcji, nie ma powodu, dla którego nie mogą być reprezentowane jako bity / bajty.

Masz już reprezentację tej funkcji jako tekstu. Konwertuj każdy znak na wartość jednobajtową przy użyciu kodowania ASCII. Następnie wynikiem jest sekwencja bajtów, tj. Sekwencja bitów, tj. Ciąg znaków nad alfabetem . To jeden przykład kodowania.$\{0,1\}^*$

Nie mogę się oprzeć ...

⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂
⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼⠀
⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠⠀
⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀
⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆
⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

⢱⠀
⢸⠁
⠊

(Kropki powyżej reprezentują je, puste pola zerowe).

Twój komputer przechowuje wszystko jako sekwencje 0i1 , w tym pytanie, które wpisałeś, aby zapytać, jak to robi. Na przykład każda litera i symbol są reprezentowane przez 8-bitów (mówię o tym, jak kiedyś było, obecnie jest to 16-bitów i jest bardziej skomplikowane). Możesz je zobaczyć tutaj . Nie pokazują bitów, a raczej kody szesnastkowe i ósemkowe. Czy wiesz, jak przekonwertować liczbę na cyfrową reprezentację?

Fundamentalną hipotezą tej koncepcji jest teza Kościoła Turinga . Może być trudno zauważyć, że dowolny algorytm może być reprezentowany jako ciąg bitów, ponieważ pojęcie „algorytm” można traktować bardzo nieformalnie. W tezie Church-Turing używają bardzo rygorystycznie zdefiniowanej koncepcji algorytmu (i nawet wtedy pojawiło się kilka pytań dotyczących słów). Jednak ich terminologia ma zdobyć tak wiele kołysać się, że jest czasami argumentował, że te definicje dla takich słów, jak „algorytm” są tak skuteczne, że po prostu przyjąć je jako tej definicji.

Church-Turing stwierdza, że ​​każdy algorytm może być zaimplementowany jako obliczenie na maszynie Turinga. Biorąc pod uwagę, że opis maszyny Turinga jest skończonym zestawem wartości, banalne jest sprawdzenie, jak odwzorować ten opis na ciąg liczb, a następnie na ciąg zer i jedynek.

Jak wspomniano w innych odpowiedziach, reprezentowanie przykładowego algorytmu za pomocą kodowania ASCII lub innych kodowań jest banalne.

Myślę, że powód, dla którego twoja książka podaje to stwierdzenie jako fakt, wynika z faktu, że wielu po prostu używa tezy Turinga jako podstawy do zdefiniowania algorytmu. Jeśli użyjesz takiej definicji, jest to tak oczywiste, jak fakt, że „5 to liczba”, ponieważ w zasadzie ją zdefiniowałeś.

To stwierdzenie opiera się na istnieniu uniwersalnych baz TM . Są to w zasadzie programowalne TM, które mogą symulować dowolną inną TM z co najwyżej poli narzutami. Dlatego twój program jest po prostu częścią danych wejściowych zakodowanych jako zera i jedynki.

Porozmawiajmy o algorytmach, które nie mogą być reprezentowane jako skończony ciąg bitów dla dowolnego rodzaju kodowania.

Pozwól, że napiszę dla ciebie taki algorytm ... Ach, ale jeśli to zrobię, mogę przedstawić ten algorytm za pomocą kodowania mojego wpisanego tekstu.

Co powiesz na reprezentowanie mojego algorytmu za pomocą jakichś „analogowych środków”, powiedzmy przez pozycję kilku monet na moim biurku. Chociaż położenie tych monet można modelować za pomocą liczb rzeczywistych (które mogą w niektórych przypadkach kodowaniach mogą być niemożliwe do skończonego przedstawienia), cały ten opis można ponownie uznać za reprezentację mojego algorytmu i można go ponownie zakodować na ciąg bitów!

Mam nadzieję, że te przykłady wyjaśniają, że jeśli jakiś algorytm nie może być reprezentowany przez skończony ciąg bitów, w ogóle nie mamy możliwości opisania tego algorytmu!

Dlaczego więc mielibyśmy rozważyć istnienie czegoś, o czym nie możemy mówić? Być może interesujące dla filozofii, ale nie dla nauki. Dlatego definiujemy pojęcie algorytmu tak, aby mogło być reprezentowane przez ciąg bitów, ponieważ wtedy przynajmniej wiemy, że jesteśmy w stanie mówić o wszystkich algorytmach.

Chociaż powyższa odpowiedź odpowiada na zadane pytanie, myślę, że zamieszanie w podanym przykładzie wynika głównie z faktu, że reprezentacja musi jedynie jednoznacznie reprezentować jakiś algorytm. Sposób reprezentacji nie musi obejmować faktycznych obliczeń wywoływanych przez algorytm! Jest to bardzo przydatne, ponieważ oznacza, że ​​możemy reprezentować algorytmy nieobliczalne !

Innym sposobem na sprawdzenie tego jest teoria informacji. Wszystkie kodowania znaczących / przydatnych informacji / pytań można przekształcić w binarne „sekwencje”.

Znaczna część pola dotyczy pytania „w jaki sposób zadawać najmniej średnią liczbę pytań w celu przekazania znaczącej informacji?” W praktyce jest to to samo, co „jakie jest optymalne podejście do zadawania najmniejszej liczby pytań typu tak / nie, aby zrozumieć, co zostało przekazane lub powiedziane?”