Czym dokładnie jest obliczenie?

Wiem, czym jest obliczenie w jakimś niejasnym sensie (tak robią komputery), ale chciałbym bardziej rygorystyczną definicję.

Dictionary.comDefinicje obliczeń, obliczeń, obliczeń i obliczeń są okrągłe, więc to nie pomaga.

Wikipediadefiniuje obliczenia jako „każdy rodzaj obliczeń zgodny z dobrze zdefiniowanym modelem”. Definiuje obliczenia jako „zamierzony proces, który przekształca jeden lub więcej danych wejściowych w jeden lub więcej wyników ze zmianą zmiennych”. Wydaje się jednak, że ta definicja obejmuje wiele działań jako obliczeń, mimo że zwykle nie są one uważane za obliczenia.

Na przykład, czy nie oznacza to, że powiedzmy, że eksplodująca bomba jest obliczeniem, przy czym wejście jest zapalonym bezpiecznikiem, a wyjście eksplozją?

Czym więc jest obliczenie?

Być może problemem jest poszukiwanie bardzo konkretnej definicji bardzo ogólnej koncepcji. Nie widzę problemu oglądania praktycznie wszystkiego jako obliczenia. Chociaż nie myślimy o tym, wszystko, co robimy, można wyrazić w kategoriach fizyki części składowych, aż do bzyczących kwarków. Z obliczeniami mamy tę samą sytuację. Są dane wejściowe, wyjściowe i proces (wszystkie mogą być trywialne). To, czy są interesujące czy przydatne jako obliczenia, czy modele obliczeniowe, to zupełnie inna kwestia.

Najsilniejsza robocza definicja, jaką mamy, pochodzi z (silnej) tezy Church-Turinga, która stwierdza, że ​​każdy możliwy fizycznie możliwy do zrealizowania model obliczeniowy nie jest potężniejszy niż Maszyna Turinga. Jeśli uważasz, że jest to prawdą, to chociaż możemy mieć wiele sposobów wyrażania rzeczy, ostatecznie możemy zredukować każde obliczenie do maszyny Turinga, stąd podając definicję obliczenia jako „wszystko, co możemy zredukować do maszyny Turinga”.

W tym modelu wybuchająca bomba jest obliczeniem. Nie jest to powszechnie stosowane (mamy nadzieję;)), ale możemy w pewien sposób modelować za pomocą maszyny Turinga (choć tutaj jest spór o naturę wyniku i równoważność z wyjściem TM). Nie jest to również ogólnie dobry model obliczeń, ponieważ wydaje się mało prawdopodobne, aby model wybuchającej bomby był kompletny w Turingu.

Oto pytanie, które Turing postanowił rozwiązać w swoim słynnym artykule z 1936 r. Pt. „Liczby obliczalne”, stosując aplikację do Entscheidungsproblem , pracy, w której wymyślił (tak zwaną) model maszyny Turinga. W szczególności sekcja 9.

Praca Turinga jest w kontekście liczb obliczalnych . Istnieją inne pojęcia obliczeń odpowiednie do obliczania innych rodzajów struktur, a ich badania stanowią część teorii obliczeń (znanej również jako teoria rekurencji).

Główną różnicą między powszechnym pojęciem obliczeń a twoim przykładem (eksplodująca bomba) jest rzecz obliczana. Co oblicza eksplodująca bomba? Kolejną różnicą są środki obliczeniowe, ale można sobie wyobrazić mechaniczny sprzęt, który wykorzystuje bomby do obliczenia czegoś bardziej uzasadnionego.

Inna kwestia dotyczy tego, czy klasyczne pojęcia obliczeń odnoszą się do tego, co postrzegamy dzisiaj jako obliczenia - mianowicie do dwukierunkowej interakcji między komputerem a użytkownikiem. Jest to powszechna krytyka w stosunku do klasycznego pojęcia obliczalności, chociaż interakcję można modelować za pomocą narzędzi teorii obliczeń (to nie jest to, czego uczysz się w klasie).

To na poziomie najbardziej podstawowego, obliczenie jest tylko mapowanie pomiędzy pewnym zbiorze w pewnym zbiorze . każdy nazywa wejście i obliczanie odwzorowuje to wejście do pewnego wyjściowego . Odwzorowanie należy zdefiniować w całej domenie: jeśli niektóre dane wejściowe nie są odwzorowane przez obliczenia, wówczas obliczenia na nie są zdefiniowane. ⁽¹⁾B x ∈ A y ∈ B x ∈ A $A$$B$$x\in A$$y\in B$$x\in A$$x$

Inne świetne odpowiedzi w tym wątku próbują wykreślić związek między tym odwzorowaniem a metodą jego osiągnięcia. Wyjaśniają, że aby „obliczyć” dane wyjściowe niektórych danych wejściowych , potrzebujemy systematycznej, dobrze zdefiniowanej metody, która prowadzi nas od danych wejściowych do danych wyjściowych . Chociaż jest to prawda, nie jest to konieczne do zdefiniowania obliczeń. Rzeczywiście, jeśli napotkasz dżina i za każdym razem, gdy podasz mu liczbę , odpowiedzą , wtedy coś obliczą (nawet jeśli to odwzorowanie nie jest rekurencyjne i żaden komputer nie może tego wygenerować).x y x $x$$x$$y$$x$$y$

W tym bardzo szerokim spojrzeniu na obliczenia, każde urządzenie fizyczne jest komputerem: przenosi system fizyczny w czasie (jego dane wejściowe) do innego systemu w czasie (dane wyjściowe). Co więcej, to obliczenie jest dobrze zdefiniowane (tzn. Może być określone w zwarty sposób, np. Za pomocą macierzy jednolitych). Jeśli odpowiednio zaprojektujesz urządzenie, może ono wykonać prawie dowolne (rekurencyjne) obliczenia, jakie chcesz. (Scott Aaronson mówi dość dużo o „problemach z obliczaniem natury”, chociaż skupia się głównie na problemach z NP-zupełnością, jest to bardzo istotne w tej dyskusji).t = $t=0$$t=1$

Konkluzja: każde mapowanie definiuje obliczenia. Każde „urządzenie”, które przekształca dane wejściowe na odpowiednie dane wyjściowe, wykonuje („oblicza”) określone obliczenia.

⁽¹⁾ możemy rozszerzyć dyskusję na tego rodzaju obliczenia, co będzie miało sens, gdy pomyślisz o funkcjach, które nie są rekurencyjne, ale wolę tam nie wchodzić.

Nie będę próbował definiować, czym jest obliczenie, co całkiem dobrze zrobili Luke Mathieson i Yuval Filmus.

Jednak myślenie o urządzeniu wybuchającym jako obliczeniu doprowadziło mnie do ważnej kwestii pobocznej: jeśli eksplozja jest obliczeniem, to co ona oblicza? Inne niż przedstawienie urządzenia po jego wybuchu.

Moim celem jest to, abyśmy mogli dość dokładnie zdefiniować to, co uważamy za obliczenie, a nawet to, co można postrzegać (wymyślone?) Jako jedno. Możemy opisać obliczenia. Ale czy możemy powiedzieć, co to komputer?

Obliczenia, jak to jest powszechnie definiowane, to czysto syntaktyczna gra. Jest to gra struktur fizycznych przekształcanych według precyzyjnych reguł. Ponieważ naszym jedynym narzędziem (do standardowych przekształceń) do reprezentowania struktur fizycznych jest ostatecznie ciąg symboli, obliczenia są ostatecznie definiowane jako pewnego rodzaju formalne przekształcenia ciągów symboli. Dotyczy to maszyn Turinga, rachunku lambda, częściowych funkcji rekurencyjnych i innych mniej popularnych modeli. Słowo rachunek różniczkowy (jak w rachunku różniczkowym lambda) faktycznie odzwierciedla ten pogląd, ponieważ w języku łacińskim rachunek różniczkowy i pokwitujący to małe kamienie używane do przedstawienia.

Ale to nie mówi, jakie znaczenie należy przypisać tej składni, co ona reprezentuje. Oto, co myślę, niewiele rozumiem, ponieważ nie jestem specjalistą od takich zagadnień (więc sprawdź mnie dwukrotnie). Problem obejmuje teoria modeli .

Biorąc pod uwagę formalny system reprezentacji, prawdopodobnie związany z logiką (aksjomaty i reguły wnioskowania) lub systemem obliczeniowym (reguły transformacji), model teorii formalnej jest strukturą matematyczną z komponentami zgodnymi z tymi regułami.

To samo obliczenie, a ściślej ten sam opis obliczenia może faktycznie mieć wiele modeli odpowiadających bardzo różnym bytom.

Na przykład algorytm GCD opisuje obliczenia. Ale może być interpretowane na liczbach naturalnych lub na wielomianach.

Przypomina to cytat Bertranda Russella :

Matematykę można zdefiniować jako przedmiot, w którym nigdy nie wiemy, o czym mówimy, ani czy to, co mówimy, jest prawdą.

Sytuacja jest prawie taka sama w przypadku obliczeń. Jest to formalna gra, w której ruchy można zrozumieć na wiele różnych sposobów. Ale tak naprawdę istnieją głębokie powiązania między matematyką formalnie zdefiniowaną przez systemy aksjomatyczne a teorią obliczeń.

Obliczenia, algorytmika zostały zdefiniowane w celu rozwiązania problemów matematycznych, a wiele współczesnych koncepcji zostało wymyślonych przez logików, którzy starali się zrozumieć mechanizmy, które pozwalają nam udowodnić twierdzenia, zaczynając od aksjomatów i stosując reguły wnioskowania.

Stąd, aby powrócić do eksplodującego urządzenia, z pewnością można je interpretować jako manipulację reprezentacją, tj. Jako obliczenie. Ale generalnie bardzo trudno jest skojarzyć z nim jakiekolwiek znaczenie poza samym sobą.

Jednak nie zawsze tak jest lub nie było. Zasada obliczeń analogowych opiera się na założeniu, że do obliczeń powiązanych w określony sposób można zastosować inny system reprezentacji. Następnie możemy obliczyć za pomocą jednego systemu, aby mieć wyobrażenie o tym, co drugi system (zbyt nieporęczny, aby go użyć, na przykład wszechświat :), obliczy w odpowiednim ustawieniu.

Lubię odpowiadać na tego rodzaju pytania dotyczące terminologii w kategoriach etymologicznych.

Tak więc obliczenia pochodzą od łacińskiego słowa compŭtus, co dosłownie oznacza „obliczenie”.

W językach łacińskich, takich jak francuski, włoski, hiszpański lub portugalski (między innymi), ta etymologia jest wspólna z „opowiadaniem” (opowiadaniem) w języku francuskim compte / conte w języku hiszpańskim cuenta / cuento w języku portugalskim conta / conto itp ...

Obliczenie polega więc na obliczeniu i opowiedzeniu, w jaki sposób dokonano tego obliczenia.

Dlatego powiedziałbym, że obliczenia są procesem wykorzystywania reguł matematycznych i logicznych do przetwarzania danych informacji, dzięki czemu nowe oryginalne informacje są wydedukowane z oryginalnych danych, śledząc, w jaki sposób te nowe informacje zostały wygenerowane (procesor, pamięć, dane wejściowe i wyniki są wtedy podstawami)