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

17

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 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\}^*$

— Kenenbek Arzymatov
źródło

38

Nie znasz absolutnej minimalnej wymaganej wiedzy, aby zrozumieć, w jaki sposób kodowany jest tekst. Dzisiaj jest wspaniały dzień do nauki! joelonsoftware.com/2003/10/08/…

— Eric Lippert,

1

Myślę, że OP może przyjść do tego z innego punktu widzenia, opartego na dwuznaczności w cytowanym tekście. Wydaje mi się, że OP oznacza „jak można zbudować całą maszynę i algorytm jako ciąg bitów”, a nie dane wejściowe do samej maszyny Turinga. Cytowany tekst sugeruje, że cały algorytm może być wykonywany samodzielnie, ale kodowany w utf kawałek języka c nie mówi nic o tym, jak maszyna faktycznie działałaby na tym ciągu.

— Sentinel,

3

... Myślę, że wszyscy tutaj nie rozumieją źródła i zbyt daleko idą na żart, kosztem braku doświadczenia Romów. Większość tych komentarzy i odpowiedzi mówi o kodowaniu tekstu do arbitralnej transmisji, podczas gdy cytat mówi o kodowaniu algorytmu do konsumpcji przez maszynę Turinga. (Obecnie) zaakceptowana odpowiedź przynajmniej dotyka jej w drugim zdaniu.

— Izkata

2

@Izkata Nie jestem pewien, czy wiesz, że ze względu na uniwersalność te dwa stwierdzenia są równoważne.

— Konrad Rudolph

15

Zabawne jest to, że aby móc odczytać kodowany algorytm, trzeba go było zmienić w ciąg bitów, jak tylko go wpiszesz. Nigdy nie był reprezentowany inaczej - od klawiatury po monitor. Miał reprezentację niebinarną tylko w naszych umysłach; a na poziomie fizjologicznym, kiedy patrzysz na synapsy, nawet to jest dyskusyjne.

— Peter - przywróć Monikę

45

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.

— Daniel F.
źródło

Jak dokładnie reprezentujesz maszynę Turinga jako listę instrukcji? Zwykła definicja jest mniej więcej taka .

— svick

@svick Jak wspomniano w mojej odpowiedzi poniżej, używasz uniwersalnej TM, która przyjmuje opis TM jako dane wejściowe (zakodowane w odpowiedni sposób)

— dseuss

@svick Język programowania z prostymi instrukcjami, aby przesunąć wskaźnik na taśmę? Myślę, że przykładem takiego może być ezoteryczny język programowania Brainfuck . Przykładowy kod

— LukStorms

@LukStorms Nie sądzę, że można już nazywać to „maszyną Turinga”.

— svick

52

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\}^*$

— DW
źródło

Dokładnie. I jak powiedziałem powyżej, stało się to, gdy Roma to napisała. Nawet glify, które widzę na monitorze, to czarno-białe piksele, tj. Informacje binarne, przesyłane przez połączenie danych binarnych z pamięci binarnej podłączonej do sieci binarnej za pośrednictwem sterowników binarnych. Czy można przedstawić każdy algorytm jako ciąg bitów? Co więcej: jest to nieuniknione, chyba że ograniczysz się do mediów analogowych i bezpośredniej komunikacji.

— Peter - przywróć Monikę

@ PeterA.Schneider Korzystanie z mediów analogowych lub twarzą w twarz niekoniecznie oznacza, że nie ma wbudowanego dyskretnego kodowania. Używanie języka naturalnego nie jest dalekie od używania dyskretnego kodowania, prawda?

— Jean-Baptiste Yunès,

32

Nie mogę się oprzeć ...

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

⢱⠀
⢸⠁
⠊

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

— po lewej stronie
źródło

5

Zabawne (+1), ale służy podkreśleniu zasadniczo arbitralnej natury kodowania.

— John Coleman,

4

Miłej zabawy pisanie kompilatora do tego :)

— Barmar

Przypomina mi stackoverflow.com/questions/5508110/…

— MSalters

1

@Barmar Brzmi jak wyzwanie dla codegolf.stackexchange.com

— IMSoP

1

@RomaKarageorgievich oto funkcja renderująca znaki brajlowskie. Oto proste opakowanie, które pozwala wywoływać je z wiersza poleceń.

— lewo około

13

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ę?

— Andrej Bauer
źródło

6

Ma 16 bajtów tylko w systemie Windows i niektórych bibliotekach, takich jak Qt lub ICU, które używają UTF-16. I nawet nie wszystkie litery zajmują ogólnie jedną jednostkę kodu, nawet w UTF-32, więc mogą być dłuższe. Dlatego myślę, że lepiej trzymać się ASCII w tej dyskusji, wprowadzenie Unicode tutaj będzie dość komplikować.

— Ruslan

8

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ś.

— Cort Ammon - Przywróć Monikę
źródło

9

Teza Church-Turinga nie jest twierdzeniem i nie obejmuje żadnej definicji pojęcia algorytmu, która jest nieformalna. Nie widzę też potrzeby powoływania się na tezę Turinga. „Głębokim” powodem, dla którego niektóre obiekty mogą być reprezentowane jako ciągi skończone, a niektóre nie, jest to, że niektóre zbiory są policzalne, a niektóre nie.

— quicksort

Widzę „algorytm można zakodować jako ciąg, jeśli określimy zastrzyk między składnikami specyfikacji maszyny a zestawem ciągów w języku”. OP robi to w swoim przykładzie, biorąc maszynę reprezentowaną przez „ $ (x + 1) ^ 2 $ ” i ponownie reprezentując ją jako ciąg znaków w języku dobrze uformowanych funkcji C (lub BCPL, C ++, i in.) .

— Eric Towers

1

@EricTowers Który wymaga tezy Church-Turinga. W przeciwnym razie nie można mieć pewności, że istnieje specyfikacja maszyny dla algorytmu dla wszystkich algorytmów.

— Cort Ammon - Przywróć Monikę

1

Twierdzę, że „algorytm [wymagający] wyrażenia niezliczonej liczby symboli” nie może być wyrażony. Takie wyrażenie musi zawierać niezliczoną liczbę symboli, w przeciwnym razie może być wyrażone w mniejszym języku podrzędnym. Ponadto, każde (niemądre) wyrażenie na nieskończonym alfabecie ma nieskończoną ilość entropii w prawie wszystkich swoich symbolach, więc przeciwstawia się wyrażeniu (tzn. Nie może faktycznie komunikować się z odbiorcą). Wszelka logika finansowa odmawia działania na takich nieskończonych ciągach i nie jestem świadoma logiki nieskończonej, która pozwoli na pracę na niepoliczalnych ciągach.

— Eric Towers

1

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

— DW

4

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.

— dseuss
źródło

1

@Discretelizard, nie podążam za tobą. Każdy algorytm można wyrazić jako dane wejściowe do uniwersalnej bazy TM. Języki mogą być obliczalne lub nieobliczalne; Nie znam żadnego standardowego pojęcia obliczalności algorytmów, więc nie jestem pewien, do czego zmierzasz. Co by to znaczyło mieć algorytm nieobliczalny? Być może myślisz o algorytmach, które niekoniecznie kończą się? Ale uniwersalna TM wciąż może uruchamiać takie algorytmy.

— DW

@Discretelizard Też cię nie śledzę. Możliwość uruchomienia na maszynie Turinga jest zasadniczo definicją algorytmu. Przypuszczam, że mógłbyś mówić o „algorytmie” dla, powiedzmy, maszyny Turinga z wyrocznią dla problemu zatrzymania, ale zwykle „algorytm” oznacza „rzecz, którą możesz zrobić na maszynie Turinga”.

— David Richerby,

@DavidRicherby Prawda, jak sądzę, faktyczna definicja algorytmu jest bardziej rygorystyczna. Ale to pytanie dotyczy tego, dlaczego nakładamy znacznie łagodniejsze ograniczenie, a stwierdzenie, że istnieje jeszcze silniejsze ograniczenie, nie jest moim zdaniem bardzo pouczające.

— Dyskretna jaszczurka

4

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 !

— Dyskretna jaszczurka
źródło

„jeśli jakiś algorytm nie może być reprezentowany przez skończony ciąg bitów, nie mamy możliwości opisania tego algorytmu!” - To nie do końca prawda. Można powiedzieć: „Dla każdej liczby rzeczywistej

r

$r$ rozważ algorytm

A_{r}

$A_r$ jako ... ”. Zatem większości tych algorytmów nie da się zapisać, ale jakoś nadal je wszystkie wyraziliśmy.

— Raphael

1

A_{r}

$A_r$ jest wyraźnie reprezentacją tego algorytmu i dla wszystkich algorytmów, które chcesz reprezentować, po prostu wybierz symbol reprezentujący wartość

R

$\mathbb{R}$ . Tak więc algorytm może być reprezentowany. Zauważ, że jest to tylko jednokierunkowa implikacja, na odwrót nie trzeba trzymać.

— Dyskretna jaszczurka

1

Tak! Śliczny! Wittgenstein! „Wovon man nicht sprechen kann, darüber muss man schweigen.”

— Peter - przywróć Monikę

@Discretelizard Zabraknie symboli dla

r

$r$ szybko.

— Raphael

@Raphael Tak i? Nic dziwnego, że spisanie niezliczonej liczby algorytmów nie jest możliwe. I znowu twierdzisz, że „wyrażasz” niektóre algorytmy, których nie można zapisać. Nie rozumiem, co masz na myśli przez „ekspresowe”, ale wydaje się, że oznacza to przynajmniej reprezentację. Ponieważ moje roszczenie zaczyna się od założenia, że algorytm nie jest reprezentowany, nie widzę, w jaki sposób jest to sprzeczne z moim twierdzeniem.

— Dyskretna jaszczurka

2

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?”

— eSurfsnake
źródło