Czym dokładnie jest obliczenie?

20

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?

terminology computability

— Kelmikra
źródło

To świetne, klasyczne pytanie.

— Ran G.

Duplikat ?

— Raphael

@Raphael O ile mi wiadomo, obliczenia! = Algorytm. Być może jednak wykonanie algorytmu jest obliczeniem.

— Kelmikra

Dla mnie „P jest obliczalny” == „Istnieje algorytm, który rozwiązuje P” (dla P jakiś problem). Jednak może to wynikać z mojej perspektywy TCS.

— Raphael

@Raphael Pytanie dotyczy tego, czym jest obliczenie, a nie co to znaczy, że P jest obliczalny.

— Kelmikra

6

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.

— Luke Mathieson
źródło

2

Raczej nie na temat, ale założę się, że model eksplodującej bomby jest gotowy do Turinga! Eksplozje mogą wywołać inne eksplozje, które mogą być wykorzystane do rozprzestrzeniania sygnałów i wykonywania bram. Bomba b może być ustawiona na wybuch w danym momencie za pomocą urządzenia, ale pobliska bomba może wyłączyć urządzenie, nie powodując wybuchu b, co pozwala na brak bramek.

— Kelmikra

@ Kyth'Py1k jak domino bramy? Nie sądzę, żeby to się zakończyło, ponieważ nie można zapętlać w nieskończoność, ponieważ „obliczenia” zawsze będą się zatrzymywać w zależności od wielkości maszyny / pola minowego

— maniak ratchet,

1

@ratchetfreak Nie, chyba że szczątki bomby zostaną przetworzone w nowe bomby za pomocą nanobotów, a następnie przeniesione ...

— Kelmikra

4

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

— Yuval Filmus
źródło

Oczywiście eksplozja jest obliczeniem. „Oblicza” dokładnie jednolitą transformację opisującą wybuch. BTW, wiele razy fizycy, których spotkałem, byli „zdenerwowani”, kiedy mówicie, że (powiedzmy), że brama kwantowa oblicza jednostkę, zamiast ją rozwijać lub odpowiednio przekształcać system fizyczny („ czy brama bierze długopis i papier i oblicza unitary "?) :)

— Ran G.

Przeczytałem sekcję dziewiątą „Liczby obliczalne z aplikacją do Entscheidungsproblem”, ale to naprawdę nie pomogło. Chociaż nie przeczytałem go bardzo dokładnie, wydawało się, że stanowi to fundament dla maszyn Turinga. Czy mówisz, że obliczenia to wszystko, co można modelować jako działanie wykonywane przez maszynę Turinga? Jeśli tak, to czy prawie wszystko nie byłoby obliczeniem? Na przykład wybuchy bomb mogą być modelowane jako maszyna Turinga, tak że położenia, prędkość i rodzaje cząstek kwantowych otaczających cząstek są kodowane jako binarne.

— Kelmikra

„Co oblicza eksplodująca bomba?” Obliczana jest zmiana stanów cząstek otaczających bombę zgodnie z prawami fizyki.

— Kelmikra

„Inną kwestią jest to, czy klasyczne pojęcia obliczeń odnoszą się do tego, co postrzegamy dzisiaj jako obliczenia - mianowicie dwustronnej interakcji między komputerem a użytkownikiem”. Nie sądzę, że jest to coś, co uważa się za obliczenia. Uważa się, że roboty autonomiczne wykonują obliczenia, nawet jeśli nie muszą wchodzić w interakcje z użytkownikami.

— Kelmikra

Oto pomysł: obliczenia to proces generowania wyników w celu ułatwienia wnioskowania dokonanego przez optymalizatorów (np. Ludzi i roboty). Jak to?

— Kelmikra

1

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. ⁽¹⁾ $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$ $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=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ć.

— Ran G.
źródło

Problem z tą definicją polega na tym, że nie odpowiada ona faktycznemu użyciu słowa „obliczenie”. Komputery są uważane za wykonujące obliczenia, podczas gdy, powiedzmy, materiały wybuchowe nie są.

— Kelmikra

IMHO mapowanie jest dokładnie tym, czym nie jest obliczenie. Myślę, że mylisz składnię i semantykę. Wyraźnie rozumiesz mapowanie jako relację wejścia-wyjścia, jakkolwiek zdefiniowaną. Według wszystkich moich książek jest to semantyka. Obliczenia są środkami stosowanymi do uzyskania danych wyjściowych odpowiadających niektórym wejściom w sekwencji kroków. Chociaż możesz powiedzieć, że każde obliczenie definiuje odwzorowanie (choćby tylko syntaktyczne), myślę, że błędem jest uznanie, że odwzorowanie definiuje obliczenia, chyba że dokładnie wyjaśnisz, że przechodzisz w hiperkomputer, co wydaje się nieco poza pytaniem.

— babou

Powinienem wyjaśnić ducha mojej odpowiedzi (zdaję sobie sprawę, że nie jest ona sformułowana w ten sposób): samo mapowanie nie jest obliczeniem. Proces przekształcania wejścia na wyjście jest obliczenie tego konkretnego odwzorowania (funkcja). Próbowałem przekazać, że konkretny proces jest istotny, każdy taki proces jest obliczeniem (nawet bardzo abstrakcyjnym, np. „Wyrocznią”).

— Ran G.

1

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.

— Babou
źródło

0

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)

— Luis Sieira
źródło

W języku francuskim opowieść to po hiszpańsku „conte”, „cuento”. Podczas gdy „compte” jest obliczeniem lub rachunkiem, „cuenta” po hiszpańsku. Nie wiem, czy chociaż homofony, „compte” i „conte” mają wspólną etymologię (brak afaik „h”), ale ta wspólna etymologia wydaje się być potwierdzona w sieci. Więc cały ten biznes obliczeniowy to tylko opowieści?

— babou

Je l'ai corrigé. Nie powinienem popełniać tego rodzaju błędów, ale nadal nie jestem zbyt dobry w pisaniu francuskiego

— Luis Sieira

A może opowieści to tylko obliczenia. Bierzesz garść postaci o danej osobowości w niektórych początkowych warunkach, a reszta historii jest obliczana

— Luis Sieira

„śledzenie, w jaki sposób generowano te nowe informacje (procesor, pamięć, dane wejściowe i wyjściowe są wówczas podstawowymi elementami”). ” Czy nie oznacza to, że coś nie jest obliczeniem, chyba że podczas tego śledzi się zużycie pamięci? To nie brzmi dobrze ...

— Kelmikra