Charakteryzacje algorytmów

Ten artykuł jest uzupełnieniem artykułu Algorytm .

Charakteryzacje algorytmów są próbami sformalizowania słowa algorytm . Algorytm nie ma ogólnie przyjętej formalnej definicji. Naukowcy aktywnie pracują nad tym problemem. W tym artykule bardziej szczegółowo zostaną przedstawione niektóre „charakterystyki” pojęcia „algorytm”.

Problem definicji

W ciągu ostatnich 200 lat definicja algorytmu stała się bardziej skomplikowana i szczegółowa, ponieważ naukowcy próbowali określić ten termin. Rzeczywiście, może istnieć więcej niż jeden rodzaj „algorytmu”. Jednak większość zgadza się, że algorytm ma coś wspólnego z definiowaniem uogólnionych procesów tworzenia „wyjściowych” liczb całkowitych z innych „wejściowych” liczb całkowitych – „parametrów wejściowych” arbitralnych i nieskończonych w zakresie lub ograniczonych w zakresie, ale wciąż zmiennych – poprzez manipulację rozpoznawalne symbole (liczenie liczb) ze skończonymi zbiorami reguł, które dana osoba może wykonać za pomocą papieru i ołówka.

Najbardziej powszechnymi schematami manipulacji liczbami — zarówno w formalnej matematyce, jak i w codziennym życiu — są: (1) funkcje rekurencyjne obliczane przez osobę za pomocą papieru i ołówka oraz (2) maszyna Turinga lub jej odpowiedniki Turinga — rejestr pierwotny — model maszyny lub „przeciw-maszyny”, model maszyny o swobodnym dostępie (RAM), model maszyny o swobodnym dostępie z zapisanym programem (RASP) i jego funkcjonalny odpowiednik „komputer ” .

Kiedy zajmujemy się „arytmetyką”, tak naprawdę dokonujemy obliczeń za pomocą „funkcji rekurencyjnych” w skróconych algorytmach, których nauczyliśmy się w szkole podstawowej, na przykład dodawania i odejmowania.

Dowody na to, że każdą „funkcję rekurencyjną”, którą możemy obliczyć ręcznie, możemy obliczyć maszynowo i na odwrót – zwróć uwagę na użycie słów obliczenie kontra obliczenie – są niezwykłe. Ale ta równoważność wraz z tezą (nieudowodnionym twierdzeniem), że obejmuje to każde obliczenie / obliczenie, wskazuje, dlaczego tak duży nacisk położono na użycie maszyn równoważnych Turingowi w definicji określonych algorytmów i dlaczego sama definicja „algorytmu” często odnosi się do „ maszyny Turinga ”. Zostało to omówione bardziej szczegółowo w charakterystyce Stephena Kleene'a .

Poniżej znajdują się streszczenia bardziej znanych charakterystyk (Kleene, Markov, Knuth) wraz z tymi, które wprowadzają nowe elementy — elementy, które dodatkowo rozszerzają definicję lub przyczyniają się do jej doprecyzowania.

[ Problem matematyczny i jego wynik można uznać za dwa punkty w przestrzeni, a rozwiązanie składa się z sekwencji kroków lub łączącej je ścieżki. Jakość rozwiązania jest funkcją ścieżki. Dla ścieżki może być zdefiniowanych więcej niż jeden atrybut, np. długość, złożoność kształtu, łatwość uogólniania, trudność i tak dalej . ]

Hierarchia Chomskiego

Istnieje większy konsensus co do „charakterystyki” pojęcia „prostego algorytmu”.

Wszystkie algorytmy muszą być określone w języku formalnym, a „pojęcie prostoty” wynika z prostoty języka. Hierarchia Chomsky'ego (1956) jest hierarchią obejmującą klasy gramatyk formalnych , które generują języki formalne . Służy do klasyfikacji języków programowania i maszyn abstrakcyjnych .

Z perspektywy hierarchii Chomsky'ego , jeśli algorytm można określić na prostszym języku (niż nieograniczony), można go scharakteryzować tym rodzajem języka, w przeciwnym razie jest to typowy „algorytm nieograniczony”.

Przykłady: język makr „ogólnego przeznaczenia”, taki jak M4 , jest nieograniczony ( kompletny Turing ), ale język makr preprocesora C nie, więc każdy algorytm wyrażony w preprocesorze C jest „prostym algorytmem”.

Zobacz także Relacje między klasami złożoności .

Cechy dobrego algorytmu

Poniżej przedstawiono pożądane cechy dobrze zdefiniowanego algorytmu, omówione w Scheider i Gersting (1995):

  • Jednoznaczne operacje: algorytm musi mieć określone, nakreślone kroki. Kroki powinny być wystarczająco dokładne, aby dokładnie określić, co należy zrobić na każdym etapie.
  • Dobrze uporządkowany: Dokładna kolejność operacji wykonywanych w algorytmie powinna być konkretnie zdefiniowana.
  • Wykonalność: Wszystkie kroki algorytmu powinny być możliwe (znane również jako efektywnie obliczalne ).
  • Dane wejściowe: algorytm powinien być w stanie zaakceptować dobrze zdefiniowany zestaw danych wejściowych.
  • Dane wyjściowe: algorytm powinien dawać jakiś wynik jako wynik, aby można było uzasadnić jego poprawność.
  • Skończoność: algorytm powinien kończyć się po skończonej liczbie instrukcji.

Właściwości określonych algorytmów, które mogą być pożądane, obejmują wydajność przestrzenną i czasową , ogólność (tj. możliwość obsługi wielu danych wejściowych) lub determinizm .

1881 Negatywna reakcja Johna Venna na maszynę logiczną W. Stanleya Jevonsa z 1870 r.

Na początku 1870 roku W. Stanley Jevons przedstawił „maszynę logiczną” (Jevons 1880:200) do analizy sylogizmu lub innej formy logicznej , np. argumentu sprowadzonego do równania boolowskiego . Za pomocą tego, co Couturat (1914) nazwał „rodzajem fortepianu logicznego [,]… równości reprezentujące przesłanki… są ​​„grane” na klawiaturze podobnej do maszyny do pisania.… Kiedy wszystkie przesłanki zostały „zagrane”, panel pokazuje tylko te składniki, których suma jest równa 1, czyli… jego logiczna całość. Ta metoda mechaniczna ma przewagę nad metodą geometryczną VENNA… ”(Couturat 1914: 75).

Ze swojej strony John Venn , logik współczesny Jevonsowi, był mniej niż zachwycony, wyrażając opinię, że „nie wydaje mi się, aby jakiekolwiek obecnie znane lub prawdopodobnie odkryte urządzenia naprawdę zasługiwały na miano maszyn logicznych” (kursywa dodana, Venn 1881:120). Ale historycznie przydatne dla rozwijającego się pojęcia „algorytmu” jest jego wyjaśnienie jego negatywnej reakcji w odniesieniu do maszyny, która „może służyć naprawdę wartościowemu celowi, umożliwiając nam uniknięcie inaczej nieuniknionej pracy”:

(1) „Po pierwsze, zestawienie naszych danych w dokładnym, logicznym języku”,
(2) „Po drugie, musimy wrzucić te stwierdzenia do postaci odpowiedniej do pracy silnika – w tym przypadku redukcja każda propozycja do jej elementarnych zaprzeczeń”,
(3) „Po trzecie, istnieje połączenie lub dalsze traktowanie naszych przesłanek po takiej redukcji”,
(4) „Wreszcie wyniki muszą być interpretowane lub odczytywane. To ostatnie generalnie powoduje powstanie za dużo otwarcia na umiejętności i roztropność”.

Dochodzi do wniosku, że „nie widzę, aby jakakolwiek maszyna mogła liczyć na pomoc, z wyjątkiem trzeciego z tych kroków; tak więc wydaje się bardzo wątpliwe, czy cokolwiek tego rodzaju naprawdę zasługuje na miano silnika logicznego”. (Venn 1881: 119 –121).

1943, 1952 Charakterystyka Stephena Kleene'a

Ta sekcja jest dłuższa i bardziej szczegółowa niż inne ze względu na jej znaczenie dla tematu: Kleene jako pierwszy zaproponował, że wszystkie obliczenia / obliczenia - wszelkiego rodzaju, łącznie - mogą być równoważnie (i) obliczone przy użyciu pięciu " prymitywne operatory rekurencyjne” plus jeden operator specjalny zwany operatorem mu lub być (ii) obliczone na podstawie działań maszyny Turinga lub równoważnego modelu.

Ponadto wyraził opinię, że którykolwiek z nich byłby definicją algorytmu .

Czytelnik, który po raz pierwszy zetknie się z poniższymi słowami, może być zdezorientowany, więc przyda się krótkie wyjaśnienie. Środki obliczeniowe wykonywane ręcznie, środki obliczeniowe wykonywane przez maszynę Turinga (lub równoważną). (Czasami autor pomyka i zamienia słowa). O „funkcji” można myśleć jako o „skrzynce wejścia-wyjścia”, w której osoba umieszcza liczby naturalne zwane „argumentami” lub „parametrami” (ale tylko liczby liczące, w tym 0 — nieujemne liczby całkowite) i uzyskuje pojedynczą nieujemną liczbę liczba całkowita (konwencjonalnie nazywana „odpowiedzią”). Pomyśl o „pudełku funkcji” jako o małym człowieku, który albo oblicza ręcznie, używając „ogólnej rekurencji”, albo oblicza przez maszynę Turinga (lub równoważną maszynę).

„Efektywnie obliczalny/obliczalny” jest bardziej ogólny i oznacza „obliczalny/obliczalny za pomocą jakiejś procedury, metody, techniki… cokolwiek…”. „Ogólna rekurencja” to sposób, w jaki Kleene opisał to, co dziś nazywa się po prostu „rekursją”; jednak „prymitywna rekurencja” - obliczenie przy użyciu pięciu operatorów rekurencyjnych - jest mniejszą formą rekurencji, która nie ma dostępu do szóstego, dodatkowego operatora mu, który jest potrzebny tylko w rzadkich przypadkach. Tak więc większość życia toczy się dalej, wymagając tylko „prymitywnych funkcji rekurencyjnych”.

1943 „Teza I”, 1952 „Teza Kościoła”

W 1943 Kleene zaproponował coś, co stało się znane jako teza Churcha :

„ Teza I. Każda efektywnie obliczalna funkcja (predykat efektywnie rozstrzygalny) jest ogólnie rekurencyjna” (po raz pierwszy stwierdzona przez Kleene w 1943 r. (przedrukowana strona 274 w Davis, red. The Undecidable ; pojawia się również dosłownie w Kleene (1952) s. 300)

W skrócie: aby obliczyć dowolną funkcję, jedynymi operacjami, których człowiek potrzebuje (technicznie, formalnie), jest 6 prymitywnych operatorów „ogólnej” rekurencji (obecnie nazywanych operatorami funkcji rekurencyjnych mu ).

Pierwsze stwierdzenie Kleene'a na ten temat znajdowało się pod tytułem rozdziału „ 12. Teorie algorytmiczne ”. Później wzmocnił to w swoim tekście (1952) w następujący sposób:

„Teza I i jej odwrotność podają dokładną definicję pojęcia procedury obliczeniowej (decyzyjnej) lub algorytmu w przypadku funkcji (predykatu) liczb naturalnych” (s. 301, pogrubiona czcionka dodana dla podkreślenia)

(Użycie przez niego słowa „decyzja” i „predykat” rozszerza pojęcie obliczalności na bardziej ogólną manipulację symbolami, taką jak ma to miejsce w matematycznych „dowodach”).

Nie jest to tak zniechęcające, jak mogłoby się wydawać – „ogólna” rekurencja to po prostu sposób wykonywania codziennych operacji arytmetycznych na podstawie pięciu „operatorów” prymitywnych funkcji rekurencyjnych wraz z dodatkowym operatorem mu w razie potrzeby. Rzeczywiście, Kleene podaje 13 przykładów prymitywnych funkcji rekurencyjnych, a Boolos-Burgess-Jeffrey dodaje kilka innych, z których większość będzie znana czytelnikowi - np. dodawanie, odejmowanie, mnożenie i dzielenie, potęgowanie, funkcja CASE, konkatenacja itp., itp.; aby zapoznać się z listą, zobacz Niektóre typowe prymitywne funkcje rekurencyjne .

Dlaczego funkcje ogólnie-rekurencyjne, a nie prymitywno-rekurencyjne?

Kleene i in. (por. §55 Ogólne funkcje rekurencyjne s. 270 w Kleene 1952) musiał dodać szósty operator rekurencji zwany operatorem minimalizacji (zapisany jako operator μ lub operator mu ), ponieważ Ackermann (1925) stworzył niezwykle rosnącą funkcję — Ackermann funkcja — a Rózsa Péter (1935) stworzył ogólną metodę tworzenia funkcji rekurencyjnych przy użyciu argumentu diagonalnego Cantora , z których żadna nie mogła być opisana przez 5 operatorów funkcji prymitywno-rekurencyjnych. W odniesieniu do funkcji Ackermanna:

„… w pewnym sensie długość algorytmu obliczeniowego funkcji rekurencyjnej, która nie jest również prymitywną rekurencyjną, rośnie wraz z argumentami szybciej niż wartość jakiejkolwiek prymitywnej funkcji rekurencyjnej” (Kleene (1935) przedruk s. 246 w The Undecidable , plus przypis 13 w odniesieniu do potrzeby dodatkowego operatora, dodano pogrubioną czcionką).

Ale potrzeba operatora mu jest rzadkością. Jak wynika z powyższej listy powszechnych obliczeń Kleene'a, człowiek idzie przez życie szczęśliwie, obliczając prymitywne funkcje rekurencyjne bez obawy, że napotka potworne liczby utworzone przez funkcję Ackermanna (np. superpotęgowanie ) .

1952 „Teza Turinga”

Teza Turinga stawia hipotezę obliczalności „wszystkich funkcji obliczeniowych” przez model maszyny Turinga i jego odpowiedniki.

Aby zrobić to w skuteczny sposób, Kleene rozszerzył pojęcie „obliczalne”, poszerzając sieć - dopuszczając do pojęcia „funkcji” zarówno „funkcje całkowite”, jak i „funkcje częściowe”. Funkcja sumaryczna to taka, która jest zdefiniowana dla wszystkich liczb naturalnych (dodatnich liczb całkowitych, w tym 0). Funkcja częściowa jest zdefiniowana dla niektórych liczb naturalnych, ale nie dla wszystkich - specyfikacja „niektórych” musi być podana „z góry”. Zatem włączenie „funkcji częściowej” rozszerza pojęcie funkcji na funkcje „mniej doskonałe”. Funkcje całkowite i częściowe mogą być obliczane ręcznie lub maszynowo.

Przykłady:
„Funkcje”: obejmują „odejmowanie wspólne m − n ” i „dodawanie m + n ”
„Funkcja częściowa”: „Odejmowanie wspólne” m − n jest niezdefiniowane, gdy dozwolone są tylko liczby naturalne (dodatnie liczby całkowite i zero) jako dane wejściowe – np. 6 − 7 jest niezdefiniowane
Funkcja sumaryczna: „Dodawanie” m + n jest zdefiniowane dla wszystkich dodatnich liczb całkowitych i zera.


Obserwujemy teraz definicję „obliczalności” Kleene'a w sensie formalnym:

Definicja: „Funkcja częściowa φ jest obliczalna , jeśli istnieje maszyna M, która ją oblicza” (Kleene (1952) s. 360)
„Definicja 2.5. Funkcja n -ary f ( x 1 , ..., x n ) jest częściowo obliczalna, jeśli istnieje maszyna Turinga Z taka, że
​​f ( x 1 , ..., x n ) = Ψ Z ( n ) ( x 1 , ..., [ x n )
W tym przypadku mówimy, że [maszyna ] Z oblicza f . Jeśli dodatkowo f ( x 1 , ..., x n ) jest funkcją całkowitą, to nazywa się ją obliczalną " (Davis (1958) s. 10)

W ten sposób doszliśmy do tezy Turinga :

„Każda funkcja, która w naturalny sposób byłaby uważana za obliczalną, jest obliczalna… przez jedną z jego maszyn…” (Kleene (1952) s. 376)

Chociaż Kleene nie podał przykładów „funkcji obliczalnych”, inni mają. Na przykład Davis (1958) podaje tablice Turinga dla funkcji Stała, Następca i Tożsamość, trzech z pięciu operatorów prymitywnych funkcji rekurencyjnych :

Obliczalne przez maszynę Turinga:
Dodawanie (jest również funkcją Constant, jeśli jeden operand jest równy 0)
Inkrementacja (funkcja następna)
Wspólne odejmowanie (zdefiniowane tylko wtedy, gdy x ≥ y ). Zatem „ x - y ” jest przykładem funkcji częściowo obliczalnej.
Właściwe odejmowanie x ┴ y (jak zdefiniowano powyżej)
Funkcja identyczności: dla każdego i istnieje funkcja U Z n = Ψ Z n ( x 1 , ..., x n ), która wyrywa x i ze zbioru argumentów ( x 1 , ..., x n )
Mnożenie

Boolos – Burgess – Jeffrey (2002) podaje następujące prozą opisy maszyn Turinga dla:

mnożenie
dodawania
parzystości
2 p

W odniesieniu do licznika , abstrakcyjny model maszyny równoważny maszynie Turinga:

Przykłady Obliczalne przez maszynę Abacus (por. Boolos – Burgess – Jeffrey (2002))
Dodawanie
mnożenia
Wykład: (opis algorytmu w postaci schematu blokowego / schematu blokowego)

Demonstracje obliczalności za pomocą liczydła (Boolos – Burgess – Jeffrey (2002)) i licznika (Minsky 1967):

Sześć operatorów funkcji rekurencyjnych:
  1. Funkcja zerowa
  2. Funkcja następcy
  3. Funkcja tożsamości
  4. Funkcja kompozycji
  5. Prymitywna rekurencja (indukcyjna)
  6. Minimalizacja

Fakt, że modele liczydła/przeciwmaszyny mogą symulować funkcje rekurencyjne, stanowi dowód na to, że: Jeśli funkcja jest „obliczalna maszynowo”, to jest „obliczalna ręcznie przez częściową rekurencję”. Twierdzenie Kleene XXIX:

" Twierdzenie XXIX: "Każda obliczalna funkcja częściowa φ jest częściową rekurencyjną... " (kursywa w oryginale, s. 374).

Odwrotność pojawia się jako jego Twierdzenie XXVIII. Razem tworzą one dowód ich równoważności, twierdzenie Kleene'a XXX.

Teza Churcha-Turinga z 1952 r

Swoim Twierdzeniem XXX Kleene dowodzi równoważności dwóch „Tez” — Tezy Kościoła i Tezy Turinga. (Kleene może jedynie postawić hipotezę (domysł) prawdziwości obu tez – tych nie udowodnił ):

TWIERDZENIE XXX: Następujące klasy funkcji cząstkowych… mają tych samych członków: (a) cząstkowe funkcje rekurencyjne, (b) funkcje obliczalne…” ( s. 376)
Definicja „częściowej funkcji rekurencyjnej”: „A funkcja częściowa φ jest częściową rekurencyjną w [funkcjach częściowych] ψ 1 , ... ψ n , jeśli istnieje układ równań E, który definiuje φ rekurencyjnie z [funkcji częściowych] ψ 1 , ... ψ n " (s. 326 )

Zatem zgodnie z twierdzeniem Kleene'a XXX: każda metoda tworzenia liczb z liczb wejściowych - funkcji rekurencyjnych obliczonych ręcznie lub obliczonych przez maszynę Turinga lub równoważną - daje w wyniku „efektywnie obliczalną / obliczalną funkcję ”. Jeśli przyjmiemy hipotezę, że każde obliczenie/obliczenie można wykonać równoważnie dowolną metodą, to przyjęliśmy zarówno Twierdzenie Kleene'a XXX (równoważność), jak i Tezę Churcha-Turinga (hipoteza „każdego”).

Notatka sprzeciwu: „Algorytm to coś więcej…” Blass i Gurevich (2003)

Pomysł oddzielenia tez Churcha i Turinga od „tezy Churcha-Turinga” pojawia się nie tylko u Kleene (1952), ale także u Blassa-Gurewicza (2003). Ale chociaż są porozumienia, są też nieporozumienia:

„... nie zgadzamy się z Kleene, że pojęcie algorytmu jest tak dobrze rozumiane. W rzeczywistości pojęcie algorytmu jest obecnie bogatsze niż w czasach Turinga. Istnieją algorytmy, zarówno nowoczesnych, jak i klasycznych odmian, których nie obejmuje bezpośrednio Analiza Turinga, na przykład algorytmy, które wchodzą w interakcje z ich środowiskiem, algorytmy, których danymi wejściowymi są struktury abstrakcyjne oraz algorytmy geometryczne lub, bardziej ogólnie, algorytmy niedyskretne” (Blass-Gurevich (2003) s. 8, dodano pogrubioną czcionką)

Charakterystyka AA Markov Jr. z 1954 roku

Andrey Markov Jr. (1954) podał następującą definicję algorytmu:

„1. W matematyce „algorytm” jest powszechnie rozumiany jako dokładna recepta, określająca proces obliczeniowy, prowadzący od różnych danych początkowych do pożądanego wyniku…” „
Poniższe trzy cechy są charakterystyczne dla algorytmów i określają ich rolę w matematyce:
„a) precyzja przepisu, nie pozostawiająca miejsca na dowolność i jego powszechna zrozumiałość – określoność algorytmu;
„b) możliwość wyjścia z danymi początkowymi, które mogą zmieniać się w określonych granicach – ogólność algorytmu
; dane — rozstrzygalność algorytmu.” (s. 1)

Przyznał, że definicja ta „nie pretenduje do matematycznej precyzji” (s. 1). Jego monografia z 1954 roku była próbą dokładniejszego zdefiniowania algorytmu; widział swoją wynikową definicję - swój „normalny” algorytm - jako „odpowiednik koncepcji funkcji rekurencyjnej ” (s. 3). Jego definicja obejmowała cztery główne elementy (rozdział II.3 s. 63ff):

"1. Oddzielne kroki elementarne, z których każdy będzie wykonywany według jednej z zasad [podstawy]... [zasady podane na wstępie]
"2. …kroki o charakterze lokalnym… [W ten sposób algorytm nie zmieni więcej niż pewną liczbę symboli na lewo lub na prawo od obserwowanego słowa/symbolu] „
3. Reguły dla wzorów podstawiania… [on nazwał listę tych „schematem” algorytmu]
„4. ... sposób na rozróżnienie „końcowej zamiany” [tj. możliwego do odróżnienia stanu lub stanów „końcowych/końcowych”]

We wstępie Markov zauważył, że „całe znaczenie dla matematyki” wysiłków zmierzających do dokładniejszego zdefiniowania algorytmu byłoby „w związku z problemem konstruktywnej podstawy matematyki” (s. 2). Ian Stewart (por. Encyclopædia Britannica) podziela podobne przekonanie: „... konstruktywna analiza jest bardzo podobna do algorytmicznego ducha, co informatyka…”. Aby uzyskać więcej informacji, zobacz konstruktywną matematykę i intuicjonizm .

Rozróżnialność i lokalność : oba pojęcia pojawiły się po raz pierwszy u Turinga (1936–1937) —

„Nowe zaobserwowane kwadraty muszą być natychmiast rozpoznawalne przez komputer [ sic : komputer był człowiekiem w 1936 roku]. Myślę, że rozsądne jest założenie, że mogą to być tylko kwadraty, których odległość od najbliższego z natychmiast obserwowanych kwadratów nie przekracza pewnej ustalonej wielkości. Zostańmy przy tym, że każdy z nowo obserwowanych kwadratów mieści się w obrębie L kwadratów jednego z poprzednio obserwowanych kwadratów. (Turing (1936) s. 136 w Davis ed. Undecidable )

Lokalność pojawia się w pracach Gurevicha i Gandy'ego (1980) (których cytuje Gurevich). „Czwarta zasada dotycząca mechanizmów” Gandy'ego to „Zasada przyczynowości lokalnej”:

„Dochodzimy teraz do najważniejszej z naszych zasad. W analizie Turinga wymóg, aby działanie zależało tylko od ograniczonej części zapisu, opierał się na ludzkim ograniczeniu. Zastępujemy to fizycznym ograniczeniem, które nazywamy zasadą lokalnej przyczynowość. Jej uzasadnienie leży w skończonej prędkości rozchodzenia się efektów i sygnałów: współczesna fizyka odrzuca możliwość natychmiastowego działania na odległość”. (Gandy (1980) s. 135 w J. Barwise i in.)

1936, 1963, 1964 Charakterystyka Gödla

A _ _ _ _ _ _ _ wielu autorów — Kleene, Gurevich, Gandy itd. — cytowało, co następuje:

„Tak więc pojęcie „obliczalne” jest w pewnym określonym sensie „absolutne”, podczas gdy praktycznie wszystkie inne znane pojęcia metamatematyczne (np. możliwe do udowodnienia, definiowalne itp.) zależą zasadniczo od systemu, w odniesieniu do którego są zdefiniowane. (str. 83)

1963 : W „Notatce” z 28 sierpnia 1963, dodanej do jego słynnego artykułu O twierdzeniach formalnie nierozstrzygalnych (1931), Gödel wyraża (w przypisie) swoje przekonanie, że „ systemy formalne ” mają „charakterystyczną właściwość polegającą na tym, że rozumowanie w nich w zasadzie można całkowicie zastąpić urządzeniami mechanicznymi” (s. 616 w van Heijenoort). „…dzięki „pracom AM Turinga można teraz podać precyzyjną i bezsprzecznie adekwatną definicję ogólnego pojęcia systemu formalnego [oraz] całkowicie ogólną wersję twierdzeń VI i XI jest teraz możliwa” (s. 616). W notatce do innej pracy z 1964 r. wyraża tę samą opinię mocniej i bardziej szczegółowo.

1964 : W Postscriptum, datowanym na 1964, do artykułu przedstawionego w Institute for Advanced Study wiosną 1934, Gödel wzmocnił swoje przekonanie, że „systemy formalne” to te, które można zmechanizować:

„W konsekwencji późniejszych postępów, w szczególności faktu, że dzięki pracom AM Turinga można teraz podać precyzyjną i niewątpliwie adekwatną definicję ogólnego pojęcia systemu formalnego… Praca Turinga zawiera analizę pojęcia „ procedura mechaniczna” (alias „algorytm” lub „procedura obliczeniowa” lub „skończona procedura kombinatoryczna”). Wykazano, że koncepcja ta jest równoważna z koncepcją „maszyny Turinga”.* System formalny można po prostu zdefiniować jako dowolną procedurę mechaniczną do tworzenia formuł, zwanych formułami możliwymi do udowodnienia. . . . ” (str. 72 w Martin Davis red. The Undecidable : „Postscriptum” do „On undecidable Propositions of Formal Mathematical Systems” pojawiające się na str. 39, loc. cit.)

* oznacza przypis, w którym Gödel cytuje artykuły Alana Turinga (1937) i Emila Posta (1936), a następnie formułuje następujące intrygujące stwierdzenie:

„Jeśli chodzi o poprzednie równoważne definicje obliczalności, które jednak są znacznie mniej odpowiednie dla naszych celów, patrz Alonzo Church , Am. J. Math., tom 58 (1936) [pojawiający się w The Undecidable s. 100-102]).

Definicje Churcha obejmują tak zwaną „ rekursję ” i „ rachunek lambda ” (tj. funkcje λ-definiowalne). Jego przypis 18 mówi, że omawiał związek „efektywnej obliczalności” i „rekurencyjności” z Gödelem, ale niezależnie zakwestionował „efektywnie obliczalność” i „definiowalność λ”:

„Teraz definiujemy pojęcie… efektywnie obliczalnej funkcji liczb całkowitych dodatnich, utożsamiając je z pojęciem funkcji rekurencyjnej dodatnich liczb całkowitych 18 (lub λ-definiowalnej funkcji dodatnich liczb całkowitych.
„Zostało to już wskazane że dla każdej funkcji liczb całkowitych dodatnich, która jest efektywnie obliczalna w właśnie zdefiniowanym sensie, istnieje algorytm obliczania jej wartości
.

Z tego i następnych wynikałoby, że jeśli chodzi o Gödla, maszyna Turinga była wystarczająca, a rachunek lambda był „znacznie mniej odpowiedni”. Następnie zwraca uwagę, że jeśli chodzi o ograniczenia ludzkiego rozumu, ława przysięgłych wciąż jest nieaktualna:

(„Zauważmy, że pytanie, czy istnieją skończone procedury niemechaniczne**, które nie są równoważne z żadnym algorytmem, nie ma nic wspólnego z adekwatnością definicji „systemu formalnego” i „procedury mechanicznej”) (s. 72, loc. cit.)
„(Dla wskazanych w przypisie teorii i procedur w bardziej ogólnym sensie ** sytuacja może być inna. Należy zauważyć, że wyniki przytoczone w dopisku nie wyznaczają żadnych granic dla mocy ludzkiego rozumu, lecz raczej dla możliwości czystego formalizmu w matematyce.) (s. 73 loc. cit.)
Przypis **: „Tj. takie, które wymagają użycia abstrakcyjnych terminów na podstawie ich znaczenia. Patrz mój artykuł w Dial. 12( 1958), s. 280”. (przypis ten znajduje się na s. 72, op.cit.).

1967 Charakterystyka Minsky'ego

Minsky (1967) bez ogródek twierdzi, że „algorytm jest„ skuteczną procedurą ”i odmawia używania słowa„ algorytm ”w dalszej części swojego tekstu; w rzeczywistości jego indeks wyjaśnia, co myśli o „Algorytmie, synonimie skutecznej procedury ” ( s. 311):

„Będziemy używać tego ostatniego terminu [ skutecznej procedury ] w dalszej części. Terminy są z grubsza synonimami, ale istnieje wiele odcieni znaczeniowych używanych w różnych kontekstach, zwłaszcza w przypadku „algorytmu”” (kursywa w oryginale, s. 105 )

Inni autorzy (patrz Knuth poniżej) używają słowa „skuteczna procedura”. Prowadzi to do zastanowienia się: co Minsky rozumie przez pojęcie „skutecznej procedury”? Zaczyna od:

„…zestaw zasad, które od czasu do czasu mówią nam dokładnie, jak się zachować” (s. 106)

Ale przyznaje, że jest to przedmiotem krytyki:

„… krytyka, że ​​interpretacja zasad zależy od jakiejś osoby lub agenta” (s. 106)

Jego wyrafinowanie? Aby „określić, wraz z określeniem zasad, szczegóły mechanizmu, który ma je interpretować ”. Aby uniknąć „uciążliwego” procesu „konieczności robienia tego od nowa dla każdej indywidualnej procedury”, ma nadzieję zidentyfikować „rozsądnie jednolitą rodzinę mechanizmów przestrzegania reguł”. Jego "sformułowanie":

„(1) język , w którym mają być wyrażone zbiory zasad zachowania, oraz
„(2) pojedyncza maszyna, która może interpretować instrukcje w tym języku, a tym samym wykonywać kroki każdego określonego procesu.” (kursywa w oryginale, wszystkie cytuje ten paragraf s. 107)

Ostatecznie jednak nadal martwi się, że „pozostaje w tej sprawie aspekt subiektywny. Różni ludzie mogą nie zgadzać się co do tego, czy dany zabieg należy nazwać skutecznym” (s. 107).

Ale Minsky jest niezrażony. Natychmiast wprowadza „Analizę procesu obliczeniowego Turinga” (jego rozdział 5.2). Cytuje to, co nazywa „ tezą Turinga ”

„Każdy proces, który można naturalnie nazwać skuteczną procedurą, może być realizowany przez maszynę Turinga” (s. 108. (Minsky komentuje, że w bardziej ogólnej formie nazywa się to „tezą Churcha ”).

Po analizie „Argumentu Turinga” (jego rozdział 5.3) zauważa, że ​​„równoważność wielu intuicyjnych sformułowań” Turinga, Churcha, Kleene, Posta i Smullyana „… " lub pojęcie "absolutne". Jak ujął to Rogers [1959]:

„W tym sensie pojęcie efektywnie obliczalnej funkcji jest jedną z niewielu„ absolutnych ”koncepcji stworzonych przez współczesne prace nad podstawami matematyki” (Minsky, s. 111, cytując Rogersa, Hartleya Jr. (1959). Obecna teoria maszyny Turinga obliczalność , J. SIAM 7, 114-130.)

1967 Charakterystyka Rogersa

W swojej Teorii funkcji rekurencyjnych i efektywnej obliczalności z 1967 roku Hartley Rogers charakteryzuje „algorytm” z grubsza jako „urzędniczą (tj. deterministyczną, księgową) procedurę… stosowaną do … , odpowiednie symboliczne wyjście ” (s. 1). Następnie opisuje pojęcie „w przybliżeniu i intuicyjnie” jako mające 10 „cech”, z których 5, jak twierdzi, „praktycznie wszyscy matematycy zgodziliby się [z]” (s. 2). Pozostałe 5, jak twierdzi, „są mniej oczywiste niż *1 do *5 i co do których moglibyśmy znaleźć mniej ogólną zgodę” (s. 3).

5 „oczywistych” to:

  • 1 Algorytm to zbiór instrukcji o skończonej wielkości,
  • 2 Istnieje zdolny agent obliczeniowy,
  • 3 „Istnieją udogodnienia do wykonywania, przechowywania i pobierania kroków w obliczeniach”
  • 4 Biorąc pod uwagę numery 1 i 2, agent wykonuje obliczenia w „dyskretny sposób krokowy” bez użycia metod ciągłych lub urządzeń analogowych”,
  • 5 Agent obliczeniowy przeprowadza obliczenia dalej „bez uciekania się do przypadkowych metod lub urządzeń, np. kostek” (w przypisie Rogers zastanawia się, czy nr 4 i nr 5 to naprawdę to samo)

Pozostałe 5, które otwiera do debaty, to:

  • 6 Brak stałego ograniczenia wielkości wejść,
  • 7 Brak ustalonego ograniczenia wielkości zestawu instrukcji,
  • 8 Brak stałego ograniczenia ilości dostępnej pamięci,
  • 9 Ustalona skończona granica pojemności lub zdolności agenta obliczeniowego (Rogers ilustruje na przykładzie proste mechanizmy podobne do maszyny Post-Turinga lub maszyny licznika ),
  • 10 Ograniczenie długości obliczeń — „czy powinniśmy mieć jakiś pomysł„ z wyprzedzeniem ”, jak długo potrwają obliczenia?” (str. 5). Rogers wymaga „jedynie, aby obliczenia kończyły się po skończonej liczbie kroków; nie nalegamy na a priori możliwość oszacowania tej liczby”. (str. 5).

1968, 1973 Charakterystyka Knutha

Knuth (1968, 1973) podał listę pięciu właściwości, które są powszechnie akceptowane jako wymagania dla algorytmu:

  1. Skończoność : „Algorytm musi zawsze kończyć się po skończonej liczbie kroków… bardzo skończonej liczbie, rozsądnej liczbie”
  2. Definitywność : „Każdy krok algorytmu musi być precyzyjnie zdefiniowany; działania, które mają zostać przeprowadzone, muszą być rygorystycznie i jednoznacznie określone dla każdego przypadku”
  3. Dane wejściowe : „… wielkości, które są mu podawane na początku przed rozpoczęciem algorytmu. Te dane wejściowe są pobierane z określonych zestawów obiektów”
  4. Wyjście : „… wielkości, które mają określony stosunek do danych wejściowych”
  5. Efektywność : „... wszystkie operacje, które mają być wykonane w algorytmie, muszą być na tyle podstawowe, aby w zasadzie mogły być wykonane dokładnie iw skończonym czasie przez człowieka używającego papieru i ołówka”

Knuth podaje jako przykład algorytm euklidesowy do wyznaczania największego wspólnego dzielnika dwóch liczb naturalnych (por. Knuth t. 1 s. 2).

Knuth przyznaje, że chociaż jego opis algorytmu może być intuicyjnie jasny, brakuje mu formalnego rygoru, ponieważ nie jest do końca jasne, co oznacza „precyzyjnie określony”, „rygorystycznie i jednoznacznie określony” lub „wystarczająco podstawowy” i tak naprzód. Czyni wysiłki w tym kierunku w swoim pierwszym tomie, w którym szczegółowo definiuje to, co nazywa „ językiem maszynowym ” dla swojego „mitycznego MIX … pierwszego na świecie wielonienasyconego komputera” (s. 120ff). Wiele algorytmów w jego książkach jest napisanych w języku MIX. Posługuje się również diagramami drzewiastymi , diagramami blokowymi i diagramami stanu .

„Dobroć” algorytmu, „najlepsze” algorytmy : Knuth stwierdza, że ​​​​„W praktyce nie tylko chcemy algorytmów, chcemy dobrych algorytmów…” Sugeruje, że niektóre kryteria dobroci algorytmu to liczba kroków do wykonania algorytm, jego „przystosowanie do komputerów, prostota i elegancja itp.” Biorąc pod uwagę szereg algorytmów do wykonywania tych samych obliczeń, który z nich jest „najlepszy”? Nazywa ten rodzaj dociekań „analizą algorytmiczną: biorąc pod uwagę algorytm, aby określić jego charakterystykę działania” (wszystkie cytaty z tego akapitu: Knuth t. 1 s. 7)

1972 Charakterystyka Stone'a

Stone (1972) i Knuth (1968, 1973) byli w tym samym czasie profesorami na Uniwersytecie Stanforda, więc nie jest zaskakujące, jeśli istnieją podobieństwa w ich definicjach (pogrubiona czcionka została dodana dla podkreślenia):

„Podsumowując… definiujemy algorytm jako zestaw reguł , który precyzyjnie określa sekwencję operacji, tak że każda reguła jest skuteczna i określona oraz taka, że ​​​​sekwencja kończy się w skończonym czasie”. (dodano pogrubioną czcionką, s. 8)

Stone jest godny uwagi ze względu na szczegółowe omówienie tego, co składa się na „skuteczną” zasadę – jego robot , czyli osoba-działająca-jako-robot, musi mieć w sobie pewne informacje i zdolności , a jeśli nie, informacje i zdolności muszą być dostarczone w "algorytm":

„Aby ludzie postępowali zgodnie z zasadami algorytmu, reguły muszą być sformułowane tak, aby można było ich przestrzegać w sposób podobny do robota , to znaczy bez potrzeby myślenia… równanie, jego przykład] mają być przestrzegane przez kogoś, kto wie, jak wykonywać działania arytmetyczne, ale nie wie, jak wyciągnąć pierwiastek kwadratowy, to musimy również podać zestaw reguł wyciągania pierwiastka kwadratowego, aby spełnić definicję algorytm” (s. 4-5)

Co więcej, „… nie wszystkie instrukcje są dopuszczalne , ponieważ mogą wymagać od robota posiadania zdolności wykraczających poza te, które uważamy za rozsądne ”. Podaje przykład robota skonfrontowanego z pytaniem „Henryk VIII królem Anglii?” i wypisać 1, jeśli tak, a 0, jeśli nie, ale robot nie otrzymał wcześniej tych informacji. Co gorsza, jeśli robot zostanie zapytany, czy Arystoteles był królem Anglii, a robotowi podano tylko pięć imion, nie wiedziałby, co odpowiedzieć.

„Intuicyjna definicja akceptowalnej sekwencji instrukcji to taka, w której każda instrukcja jest dokładnie zdefiniowana, tak aby robot miał gwarancję, że będzie w stanie jej wykonać ” (s. 6)

Po przedstawieniu nam swojej definicji, Stone wprowadza model maszyny Turinga i stwierdza, że ​​zbiór pięciu krotek będących instrukcjami maszyny to „algorytm… znany jako program maszyny Turinga” (s. 9). Zaraz potem mówi dalej, że „ obliczenia maszyny Turinga są opisane przez stwierdzenie:

"1. Alfabet taśmy
” "2. Postać , w jakiej prezentowane są parametry [wejściowe] na taśmie
„3. Stan początkowy maszyny Turinga
„4. Forma , w jakiej odpowiedzi [wyjście] będą reprezentowane na taśmie, gdy maszyna Turinga się zatrzyma „
5. Program maszyny” (kursywa dodana, s. 10)

Ta precyzyjna recepta na to, co jest wymagane do „obliczenia”, jest w duchu tego, co nastąpi później w pracy Blassa i Gurewicza.

1995 Charakterystyka Soare'a

„ Obliczenia to proces, w którym przechodzimy od początkowo danych obiektów, zwanych danymi wejściowymi , zgodnie z ustalonym zestawem reguł, zwanych programem, procedurą lub algorytmem , przez szereg kroków i dochodzimy do końca tych kroków z ostatecznym wynik, zwany wyjściem . Algorytm , jako zbiór reguł postępowania od wejścia do wyjścia, musi być precyzyjny i określony, a każdy kolejny krok musi być jasno określony. Pojęcie obliczalności dotyczy tych obiektów, które można w zasadzie określić za pomocą obliczeń. . . „(kursywa w oryginale, pogrubiona czcionka dodana s. 3)

2000 Charakterystyka Berlinskiego

Podczas studiów w Princeton w połowie lat 60. David Berlinski był uczniem Alonzo Church (por. s. 160). Jego książka z 2000 roku The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer zawiera następującą definicję algorytmu :

„ Głosem logika:
„ algorytm to
skończona procedura,
zapisana w ustalonym słownictwie symbolicznym,
rządzona precyzyjnymi instrukcjami,
poruszająca się w dyskretnych krokach, 1, 2, 3, . . .,
którego wykonanie nie wymaga wglądu, sprytu,
intuicji, inteligencji ani bystrości,
i które prędzej czy później dobiega końca. " (pogrubiona czcionka i kursywa w oryginale, s. xviii)

2000, 2002 Charakterystyka Gurewicza

Uważna lektura Gurevicha 2000 prowadzi do wniosku (wywnioskowania?), że wierzy on, że „algorytm” jest w rzeczywistości „maszyną Turinga” lub „maszyną wskazującą ” wykonującą obliczenia. „Algorytm” to nie tylko tablica symboli, która kieruje zachowaniem maszyny, nie jest to też pojedynczy przypadek maszyny wykonującej obliczenia przy określonym zestawie parametrów wejściowych, ani też odpowiednio zaprogramowana maszyna z wyłączonym zasilaniem. ; raczej algorytm to maszyna faktycznie wykonująca dowolne obliczenia, do których jest zdolna . Gurevich nie wychodzi od razu i nie mówi tego, więc jak sformułowano powyżej, ten wniosek (wniosek?) jest z pewnością otwarty na debatę:

„… każdy algorytm może być symulowany przez maszynę Turinga… program może być symulowany, a tym samym nadawany mu precyzyjny sens przez maszynę Turinga”. (s. 1)
„Często uważa się, że problem sformalizowania pojęcia algorytmu sekwencyjnego rozwiązali Church [1936] i Turing [1936]. Na przykład według Savage'a [1987] algorytm to proces obliczeniowy zdefiniowany przez maszynę Turinga Church i Turing nie rozwiązali problemu sformalizowania pojęcia algorytmu sekwencyjnego, zamiast tego podali (różne, ale równoważne) sformalizowanie pojęcia funkcji obliczalnej, a algorytm to coś więcej niż funkcja, którą oblicza. (kursywa dodana na str. 3)
„Oczywiście pojęcia algorytmu i funkcji obliczalnej są ze sobą ściśle powiązane: z definicji funkcja obliczalna to funkcja obliczalna przez algorytm. . . . (str. 4)


W Blass i Gurevich 2002 autorzy powołują się na dialog między „Quisani” („Q”) i „Autorami” (A), używając Yiannisa Moshovakisa jako folii, w którym od razu wychodzą i stwierdzają stanowczo:

„ A: Aby zlokalizować spór, najpierw wspomnijmy o dwóch punktach zgodności. Po pierwsze, jest kilka rzeczy, które są oczywiście algorytmami według czyjejś definicji – maszyny Turinga, sekwencyjne maszyny ASM [maszyny abstrakcyjne] i tym podobne… Po drugie, na drugim biegunie znajdują się specyfikacje, które nie byłyby uważane za algorytmy w ramach jakiejkolwiek definicji, ponieważ nie dają żadnych wskazówek, jak cokolwiek obliczyć… Problem polega na tym, jak szczegółowe muszą być informacje, aby można je było uznać za algorytm […] Moshovakis zezwala na pewne rzeczy, które nazwalibyśmy tylko deklaratywnymi specyfikacjami, i prawdopodobnie użyłby słowa „implementacja” na określenie rzeczy, które nazywamy algorytmami”. (akapity połączone dla ułatwienia czytelności, 2002:22)

Takie użycie słowa „wdrożenie” trafia prosto w sedno pytania. Na początku artykułu Q podaje swoją interpretację Moshovakisa:

„…[H] e prawdopodobnie pomyślałby, że twoja praktyczna praca [Gurewicz pracuje dla Microsoftu] zmusza cię do myślenia o implementacjach bardziej niż o algorytmach. Jest całkiem chętny do utożsamiania implementacji z maszynami, ale mówi, że algorytmy to coś więcej ogólnie. Sprowadza się to do tego, że mówisz, że algorytm jest maszyną, a Moschovakis mówi, że tak nie jest. (2002:3)

Ale autorzy goszczą tutaj, mówiąc: „[L] trzymamy się„ algorytmu ”i„ maszyny ”, a czytelnik znów jest zdezorientowany. Musimy poczekać do Dershowitz i Gurevich 2007, aby uzyskać następujący komentarz do przypisu:

„… Niemniej jednak, jeśli przyjąć punkt widzenia Moshovakisa, to jest to„ implementacja ”algorytmów, które postanowiliśmy scharakteryzować”. (por. przypis 9 2007:6)

2003 Charakterystyka Blassa i Gurewicza

Blass i Gurevich opisują swoją pracę jako wyewoluowaną z rozważań nad maszynami Turinga i maszynami wskazującymi , w szczególności maszynami Kołmogorowa-Uspienskiego (maszyny KU), maszynami modyfikującymi pamięć Schönhage (SMM) i automatami łączącymi zgodnie z definicją Knutha. Prace Gandy'ego i Markowa są również określane jako wpływowi prekursorzy.

Gurevich oferuje „mocną” definicję algorytmu (dodano pogrubioną czcionką):

„… Nieformalny argument Turinga na rzecz jego tezy uzasadnia silniejszą tezę: każdy algorytm może być symulowany przez maszynę Turinga … W praktyce byłoby to śmieszne… [Niemniej] [c] jeden uogólnić Maszyny Turinga, aby każdy algorytm, nieważne jak abstrakcyjny, mógł być modelowany przez uogólnioną maszynę?… Ale załóżmy, że takie uogólnione maszyny Turinga istnieją. Jakie byłyby ich stany?… struktura pierwszego rzędu … szczególna mały zestaw instrukcji wystarcza we wszystkich przypadkach ... obliczenia jako ewolucja stanu ... może być niedeterministyczny ... może wchodzić w interakcje ze swoim środowiskiem ... [może być] równoległy i wieloagentowy ... [mógł mieć] dynamiczna semantyka … [dwie podstawy ich pracy to:] teza Turinga…[i] pojęcie struktury (pierwszego rzędu) [Tarski 1933]” (Gurewicz 2000, s. 1-2)

Powyższe wyrażenie obliczenia jako ewolucja stanu znacznie różni się od definicji Knutha i Stone'a - „algorytmu” jako programu maszyny Turinga. Odpowiada raczej temu, co Turing nazwał kompletną konfiguracją (por. definicja Turinga w Undecidable, s. 118) — i obejmuje zarówno bieżącą instrukcję (stan), jak i stan taśmy. [por. Kleene (1952) s. 375, gdzie pokazuje przykład taśmy z 6 symbolami - wszystkie inne kwadraty są puste - i jak Gödelize jej połączony status taśmy stołowej].

W przykładach algorytmów widzimy ewolucję stanu z pierwszej ręki.

1995 – Daniel Dennett: ewolucja jako proces algorytmiczny

Filozof Daniel Dennett analizuje znaczenie ewolucji jako procesu algorytmicznego w swojej książce Darwin's Dangerous Idea z 1995 roku . Dennett identyfikuje trzy kluczowe cechy algorytmu:

  • Neutralność podłoża : algorytm opiera się na swojej strukturze logicznej . Zatem konkretna forma, w jakiej manifestuje się algorytm, nie jest ważna (przykładem Dennetta jest długi podział: działa równie dobrze na papierze, na pergaminie, na ekranie komputera, przy użyciu neonów lub pisma na niebie). (str. 51)
  • Podstawowa bezmyślność : bez względu na to, jak skomplikowany może być produkt końcowy procesu algorytmicznego, każdy krok algorytmu jest wystarczająco prosty, aby mógł go wykonać mechaniczne urządzenie pozbawione świadomości. Algorytm nie wymaga „mózgu” do jego utrzymania lub obsługi. „Standardowa analogia podręcznikowa wskazuje, że algorytmy to przepisy , których przestrzegają początkujący kucharze” (s. 51).
  • Gwarantowane wyniki : Jeśli algorytm jest wykonywany poprawnie, zawsze będzie dawał takie same wyniki. „Algorytm to niezawodny przepis”. (str. 51)

To na podstawie tej analizy Dennett dochodzi do wniosku, że „według Darwina ewolucja jest procesem algorytmicznym”. (str. 60).

Jednak na poprzedniej stronie poszedł na znacznie dalej. [ według kogo? ] W kontekście swojego rozdziału zatytułowanego „Procesy jako algorytmy” stwierdza:

„Ale w takim razie… czy są w ogóle jakieś ograniczenia tego, co można uznać za proces algorytmiczny? Myślę, że odpowiedź brzmi NIE; jeśli chcesz, możesz traktować dowolny proces na poziomie abstrakcyjnym jako proces algorytmiczny… Jeśli co wydaje ci się zagadkowa jednolitość ziaren piasku [oceanicznego] lub wytrzymałość ostrza [stalowego], algorytmiczne wyjaśnienie jest tym, co zaspokoi twoją ciekawość — i będzie to prawda
... jak imponujące są produkty algorytmu, podstawowy proces zawsze składa się wyłącznie z zestawu pojedynczych [ sic ] bezmyślnych kroków następujących po sobie bez pomocy jakiegokolwiek inteligentnego nadzoru; są „automatyczne” z definicji: działanie automatu. ”(s. 59)

Z powyższego nie jest jasne, czy Dennett twierdzi, że świat fizyczny sam w sobie i bez obserwatorów jest z natury algorytmiczny (obliczeniowy), czy też obserwator przetwarzający symbole jest tym, co dodaje „znaczenie” obserwacjom.

2002 John Searle dodaje wyjaśniające zastrzeżenie do charakterystyki Dennetta

Daniel Dennett jest zwolennikiem silnej sztucznej inteligencji : idei, że logiczna struktura algorytmu jest wystarczająca do wyjaśnienia umysłu . John Searle , twórca eksperymentu myślowego w chińskim pokoju , twierdzi, że „ składnia [czyli struktura logiczna] sama w sobie nie wystarcza dla treści semantycznej [czyli znaczenia]” ( Searle 2002 , s. 16). Innymi słowy, „znaczenie” symboli zależy od umysłu, który ich używa; algorytm — konstrukcja logiczna — sam w sobie jest niewystarczający dla umysłu.

Searle ostrzega tych, którzy twierdzą, że procesy algorytmiczne (obliczeniowe) są nierozerwalnie związane z naturą (na przykład kosmolodzy, fizycy, chemicy itp.):

Obliczenia […] są zależne od obserwatora, a to dlatego, że obliczenia definiuje się w kategoriach manipulacji symbolami, ale pojęcie „symbolu” nie jest pojęciem fizyki czy chemii. Coś jest symbolem tylko wtedy, gdy jest używane, traktowane lub traktowane jako symbol. Argument dotyczący chińskiego pokoju pokazał, że semantyka nie jest nieodłączną częścią składni. Ale to pokazuje, że składnia nie jest nieodłączną częścią fizyki. [...] Coś jest symbolem tylko w odniesieniu do jakiegoś obserwatora, użytkownika lub agenta, który przypisuje temu symboliczną interpretację [...] można przypisać interpretację obliczeniową do czegokolwiek. Ale jeśli pytanie brzmi: „Czy świadomość jest wewnętrznie obliczeniowa?” odpowiedź brzmi: nic nie jest wewnętrznie obliczeniowe [kursywa dodana dla podkreślenia]. Obliczenie istnieje tylko w odniesieniu do jakiegoś agenta lub obserwatora, który narzuca obliczeniową interpretację jakiegoś zjawiska. To jest oczywiste. Powinienem był to zobaczyć dziesięć lat temu, ale nie widziałem.

— John Searle, Searle 2002 , s. 17

2002: Boolos-Burgess-Jeffrey specyfikacja obliczeń maszyny Turinga

Aby zapoznać się z przykładami tej metody specyfikacji zastosowanej do algorytmu dodawania „m+n”, zobacz Przykłady algorytmów.

Przykład w Boolos-Burgess-Jeffrey (2002) (s. 31–32) pokazuje precyzję wymaganą w pełnej specyfikacji algorytmu, w tym przypadku do dodania dwóch liczb: m+n. Jest podobny do powyższych wymagań dotyczących kamienia.

(i) Omówili rolę „formatu liczb” w obliczeniach i wybrali „notację podsumowującą” do reprezentowania liczb:

„Z pewnością obliczenia mogą być trudniejsze w praktyce z niektórymi notacjami niż inne… Ale… w zasadzie można to zrobić w dowolnej innej notacji, po prostu tłumacząc dane… W celu sformułowania rygorystycznie zdefiniowanego pojęcia obliczalności , wygodnie jest używać notacji monadycznej lub zapisu sumującego” (s. 25-26)

(ii) Na początku swojego przykładu określają maszynę, która ma być użyta w obliczeniach, jako maszynę Turinga . Wcześniej określili (s. 26), że maszyna Turinga będzie miała rozmaitość 4-krotek, a nie 5-krotek. Więcej informacji na temat tej konwencji można znaleźć w artykule Maszyna Turinga .

(iii) Wcześniej autorzy określili, że pozycja głowicy taśmy będzie wskazywana przez indeks dolny po prawej stronie zeskanowanego symbolu. Więcej informacji na temat tej konwencji można znaleźć w artykule Maszyna Turinga . (W dalszej części dla podkreślenia dodano pogrubioną czcionkę):

„Nie podaliśmy oficjalnej definicji tego, co to znaczy, że funkcja numeryczna może być obliczona przez maszynę Turinga , określającej, w jaki sposób dane wejściowe lub argumenty mają być reprezentowane na maszynie i jak reprezentowane są wyniki lub wartości. Nasze specyfikacje dla k- funkcji umieszczania dodatnich liczb całkowitych na dodatnie liczby całkowite są następujące:
„(a) [ Początkowy format liczb: ] Argumenty m 1 , ... m k , ... będą reprezentowane w notacji monadycznej [jednoargumentowej] przez bloki tych liczb uderzeń, każdy blok oddzielony od następnego pojedynczym odstępem, na skądinąd pustej taśmie.
Przykład: 3+2, 111B11
"(b) [ Początkowa lokalizacja głowicy, stan początkowy: ] Początkowo maszyna będzie skanować skrajną lewą jedynkę na taśmie i będzie w stanie początkowym, stanie 1.
Przykład: 3+2 , 1 1 111B11
"(c) [ Pomyślne obliczenie - format liczbowy przy zatrzymaniu: ] Jeśli funkcja, która ma zostać obliczona, przypisze wartość n argumentom, które są początkowo reprezentowane na taśmie, to maszyna ostatecznie zatrzyma się na taśmie zawierającej blok kresek, poza tym pusty...
Przykład: 3+2, 11111
"(d) [ Pomyślne obliczenie -- położenie głowicy w miejscu zatrzymania: ] W tym przypadku [c] maszyna zatrzyma skanowanie skrajnej lewej 1 na taśma...
Przykład: 3+2, 1 n 1111
"(e) [ Nieudane obliczenia -- niepowodzenie zatrzymania lub zatrzymania z niestandardowym formatem liczb: ] Jeśli funkcja, która ma zostać obliczona, nie przypisuje argumentom żadnej wartości które są początkowo reprezentowane na taśmie, wtedy maszyna albo nigdy się nie zatrzyma, albo zatrzyma się w jakiejś niestandardowej konfiguracji…” (tamże)
Przykład: B n 11111 lub B11 n 111 lub B11111 n

Ta specyfikacja jest niekompletna: wymaga lokalizacji, w której mają być umieszczone instrukcje i ich formatu w maszynie--

(iv) w TABELI maszyny skończonej lub, w przypadku uniwersalnej maszyny Turinga , na taśmie oraz
(v) w Tabeli instrukcji w określonym formacie

Ten późniejszy punkt jest ważny. Boolos-Burgess-Jeffrey demonstruje (s. 36), że przewidywalność wpisów w tablicy pozwala „zmniejszyć” tablicę poprzez ułożenie wpisów w kolejności i pominięcie stanu wejścia oraz symbolu. Rzeczywiście, przykładowe obliczenia maszyny Turinga wymagały tylko 4 kolumn, jak pokazano w poniższej tabeli (ale uwaga: zostały one przedstawione maszynie w wierszach ):

Stan qk
Zeskanowany symbol
Działanie
Następny stan qk
Stan qn
Zeskanowany symbol
Działanie
Następny stan qk
Stan qk
Akcja B
B-następny stan qkB
1-akcja
1: następny stan qk1
1 B R H 1 1 R 2 1 R H R 2
2 B P 3 2 1 R 2 2 P 3 R 2
3 B Ł 4 3 1 R 3 3 Ł 4 R 3
4 B Ł 5 4 1 mi 4 4 Ł 5 mi 4
5 B R H 5 1 Ł 5 5 R H Ł 5

2006: Twierdzenie Sipsera i jego trzy poziomy opisu

Aby zapoznać się z przykładami tej metody specyfikacji zastosowanej do algorytmu dodawania „m+n”, zobacz Przykłady algorytmów.

Sipser zaczyna od zdefiniowania „algorytmu” w następujący sposób:

„Mówiąc nieoficjalnie, algorytm jest zbiorem prostych instrukcji służących do wykonania jakiegoś zadania. Powszechne w życiu codziennym algorytmy są czasami nazywane procedurami lub przepisami (kursywa w oryginale, s. 154)
„… od teraz skupiamy się na na algorytmach. Oznacza to, że maszyna Turinga służy jedynie jako precyzyjny model do definicji algorytmu… wystarczy, że poczujemy się wystarczająco komfortowo z maszynami Turinga, aby uwierzyć, że przechwytują one wszystkie algorytmy” (s. 156)

Czy Sipser ma na myśli, że „algorytm” to tylko „instrukcje” dla maszyny Turinga, czy też jest to kombinacja „instrukcji + (określonej odmiany) maszyny Turinga”? Na przykład definiuje dwa standardowe warianty (wielotaśmowy i niedeterministyczny) swojego konkretnego wariantu (nie ten sam, co oryginał Turinga) i kontynuuje w swoich Problemach (strony 160-161), opisując cztery kolejne warianty ( jednokrotnego zapisu, podwójnie nieskończonej taśmy (tj. lewej i prawej nieskończonej), lewego resetu i „zostań w miejscu zamiast lewego”. Ponadto nakłada pewne ograniczenia. Po pierwsze, wejście musi być zakodowane jako ciąg znaków (s. 157) i mówi o kodowaniu numerycznym w kontekście teorii złożoności:

„Zauważ jednak, że jednoargumentowa notacja do kodowania liczb (jak w przypadku liczby 17 zakodowanej przez liczbę jednoargumentową 11111111111111111) nie jest rozsądna, ponieważ jest wykładniczo większa niż naprawdę rozsądne kodowanie, takie jak notacja bazowa k dla dowolnego k ≥ 2 ” . (str. 259)

Van Emde Boas komentuje podobny problem w odniesieniu do abstrakcyjnego modelu obliczeń maszyny o swobodnym dostępie (RAM), czasami używanego zamiast maszyny Turinga podczas „analizy algorytmów”: „Brak lub obecność multiplikatywnej i równoległej manipulacji bitami operacji ma znaczenie dla prawidłowego zrozumienia niektórych wyników w analizie algorytmów.

„… [T] tutaj prawie nie istnieje coś takiego jak„ niewinne ”rozszerzenie standardowego modelu pamięci RAM w jednolitych miarach czasu; albo ma się tylko arytmetykę addytywną, albo równie dobrze można by uwzględnić wszystkie rozsądne multiplikatywne i / lub bitowe Instrukcje boolowskie dotyczące małych operandów”. (Van Emde Boas, 1990:26)

Jeśli chodzi o „język opisu” algorytmów, Sipser kończy pracę, którą rozpoczęli Stone i Boolos-Burgess-Jeffrey (dodano pogrubienie). Proponuje nam trzy poziomy opisu algorytmów maszyny Turinga (s. 157):

Opis wysokiego poziomu : „w którym używamy… prozy do opisania algorytmu, ignorując szczegóły implementacji. Na tym poziomie nie musimy wspominać, jak maszyna zarządza taśmą lub głowicą”.
Opis implementacji : "w którym używamy... prozy do opisania sposobu, w jaki maszyna Turinga porusza głową i sposobu, w jaki przechowuje dane na swojej taśmie. Na tym poziomie nie podajemy szczegółów dotyczących stanów ani funkcji przejścia."
Opis formalny : „… najniższy, najbardziej szczegółowy poziom opisu… który w pełni określa stany maszyny Turinga, funkcję przejścia i tak dalej”.

2011: Janowski

W Yanofsky (2011) algorytm jest zdefiniowany jako zbiór programów, które implementują ten algorytm: zbiór wszystkich programów jest podzielony na klasy równoważności. Chociaż zestaw programów nie tworzy kategorii, zestaw algorytmów tworzy kategorię z dodatkową strukturą. Warunki opisujące, kiedy dwa programy są równoważne, okazują się relacjami koherencji, które nadają kategorii algorytmów dodatkową strukturę.

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Algorithm_characterizations&oldid=1107118075 ”