Szczegółowe instrukcje definiujące proces obliczeniowy (o którym mówi się wtedy, że jest algorytmiczny), który rozpoczyna się od dowolnego wejścia (z pewnej liczby wejść możliwych dla danego algorytmu) i od instrukcji mających na celu uzyskanie wyniku (lub wyjścia), który jest w pełni zdeterminowany przez to wejście. Algorytmami są na przykład nauczane w szkołach podstawowych reguły kolumnowego dodawania, odejmowania, mnożenia i dzielenia; w tych algorytmach możliwymi wynikami są nieujemne liczby całkowite zapisane w systemie dziesiętnym, a możliwymi wejściami – uporządkowane pary takich liczb. Na ogół nie zakłada się, że wynik musi być koniecznie uzyskany: proces stosowania algorytmu do jakiegoś możliwego wejścia (tj. proces algorytmiczny, który postępuje wychodząc od tego wejścia) może również zakończyć się bez uzyskania wyniku (wtedy mamy do czynienia z przystankiem bez wyniku) lub może nie zakończyć się w ogóle. Jeżeli proces kończy się (nie kończy się), to mówimy, że dane wejściowe są odpowiednie (nie są odpowiednie) dla danego algorytmu.
Ważnym wynikiem w tej dziedzinie jest nierozstrzygalność tzw. problemu zatrzymania (halting problem). Można skonstruować algorytm $ alfa $ taki, że nie istnieje algorytm rozstrzygający, czy pewne dowolne dane wejściowe, które są możliwe dla $ alfa $ są również odpowiednie dla $ alfa $. W szczególności można znaleźć taki algorytm $ alfa $, dla którego zbiór jego możliwych danych wejściowych jest zbiorem liczb naturalnych.
Pojęcie algorytmu jest jednym z centralnych pojęć we współczesnej matematyce, zwłaszcza w dziedzinie obliczeń. Przykład podany jest poniżej. Znalezienie numerycznego rozwiązania równań danego typu jest równoznaczne ze skonstruowaniem algorytmu, który przekształca dowolne równanie tego typu i dowolną dodatnią liczbę racjonalną $ epsilon $ w liczbę (lub zbiór liczb), która różni się od pierwiastka (pierwiastków) tego równania o mniej niż $ epsilon $. Jednak termin „proces obliczeniowy”, używany w kontekście algorytmu, nie może być rozumiany jako oznaczający jedynie obliczenia numeryczne: nawet w elementarnej algebrze stosuje się obliczenia z literami. Standardowe obliczenia arytmetyczne zawierają pewne symbole, które nie są liczbami (nawiasy, znaki równości, symbole operatorów arytmetycznych). W związku z tym celowe jest rozważenie algorytmów zawierających dowolne symbole i obiekty złożone z symboli. Najprostszym przykładem takiego obiektu jest liniowy ciąg symboli tworzących słowo. Można też rozważać obiekty „nieliniowe” – macierze algebraiczne, drzewa pochodnych pewnego języka formalnego i ogólne grafy. Intuicyjnie, najmniejszym wymaganiem stawianym wejściom i wynikom algorytmów jest to, że muszą one być obiektami konstrukcyjnymi (por. Obiekt konstrukcyjny). Pojęcie algorytmu jest więc bardzo ogólne. Można mówić o algorytmie tłumaczenia z jednego języka na drugi, o algorytmie kontrolera ruchu lotniczego (przetwarzającego informacje o ruchach samolotów według ustalonych reguł) i innych przykładach algorytmicznie opisanych procesów sterowania. W związku z tym pojęcie algorytmu jest jedną z centralnych idei w cybernetyce i informatyce.
Przykład algorytmu.
Niech możliwymi wejściami i możliwymi wynikami będą wszystkie możliwe słowa nad alfabetem $ a, b $. Przejście od słowa $ X $ do słowa $ Y $ jest „dopuszczalne” w dwóch następujących przypadkach (gdzie $ P $ oznacza dowolne słowo): 1) $ X $ jest postaci $ aP $, a $ Y $ jest postaci $ Pb $; lub 2) $ X $ jest postaci $ baP $, a $ Y $ jest postaci $ Paba $. Instrukcje formułuje się następująco: „wyznaczając jakieś słowo jako dane wejściowe, wykonuj dozwolone przejścia aż do otrzymania słowa postaci aaP; następnie zatrzymaj się i niech słowo P będzie wynikiem” . Instrukcje te tworzą algorytm, który będziemy oznaczać przez $ \mathfrak A $. Weźmy słowo $ babaa $ jako wejście. Po jednym przejściu otrzymujemy $ baaaba $; po drugim otrzymujemy $ aabaaba $. W tym przypadku algorytm zatrzymuje się z $ baaba $ jako wynikiem. Rozważmy kolejne dane wejściowe $ baaba $. Otrzymujemy kolejno: $ abaaba, baabab, abababa, bababab, babababa, …. Można pokazać, że ten proces nigdy się nie skończy (tzn. żadne z wygenerowanych słów nigdy nie zacznie się od $ aa $). Teraz weźmy $ abaab $ jako dane wejściowe. Otrzymujemy $ baabb, abbaba, bbabab $; żadne dalsze dopuszczalne przejścia nie są możliwe, a jednocześnie warunek zakończenia nie jest spełniony. Mamy przystanek bez rezultatu. Tak więc, wejście $ babaa $ jest odpowiednie dla $ ™athfrak A $, a wejścia $ baaba $ i $ abaab $ nie są.
Znaczenie algorytmów.
W nauce algorytmy spotykamy wszędzie: „ogólne” rozwiązanie problemu wymaga algorytmu. Przykładem tego jest zdolność człowieka do dodawania liczb. Nie to, że potrafi on znaleźć, prędzej czy później, sumę dowolnych dwóch liczb, ale raczej w tym sensie, że posiada on metodę unikalnego dodawania dowolnych dwóch liczb podaną w formie pisemnej, czyli algorytm dodawania, taki jak znana metoda dodawania kolumnowego. „Ogólnie” rozwiązywanie problemu formalizuje się jako rozwiązywanie problemu algorytmicznego. Problem algorytmiczny składa się z odrębnych instancji problemowych, a do rozwiązania wszystkich z nich należy znaleźć jeden algorytm. Jeśli nie ma takiego algorytmu, to mówimy, że problem algorytmiczny jest nierozwiązywalny. Tak więc problem numerycznego rozwiązywania równań danego typu oraz problem automatycznego tłumaczenia są problemami algorytmicznymi. Ich instancje problemowe polegają, odpowiednio, na znalezieniu rozwiązania numerycznego poszczególnych równań danego typu oraz na przetłumaczeniu poszczególnych wyrażeń. Inne przykłady to weryfikacja równości algebraicznych w algebrze; algorytmiczny problem rozpoznawania dedukcyjności twierdzeń z danych aksjomatów w logice matematycznej. (W logice matematycznej pojęcie algorytmu jest również ważne, ponieważ służy jako podstawa kluczowego pojęcia rachunku, który jest uogólnieniem i bardziej precyzyjną formą intuicyjnych pojęć „dowodu” i „wykazania”). Ustalenie nierozwiązywalności danego problemu algorytmicznego (np. problemu ustalania prawdziwości lub demonstracyjności zdań w jakimś języku logiczno-matematycznym) jest ważne, ponieważ pokazuje, że w zasadzie konkretne instancje tego problemu mogą być rozwiązane tylko metodami, które są specyficzne dla każdej indywidualnej instancji problemu.
Naukowe znaczenie pojęcia algorytmu było dostrzegane od dawna. Od najdawniejszych czasów ludzie poszukiwali konstruktywnych metod rozwiązywania problemów matematycznych. Takie wysiłki zwykle korzystały z nowej dostępności odpowiednich notacji symbolicznych. Proces ten wniósł znaczący wkład do wiedzy naukowej, zwłaszcza gdy stało się jasne, że niektóre problemy są z natury nierozwiązywalne (kwadratura koła itp.). Po stwierdzeniu, że pewnych problemów nie da się rozwiązać za pomocą bezpośrednich obliczeń, w XIX wieku narodziło się teoretyczne pojęcie zbioru. Dopiero po okresie gwałtownego rozwoju tej koncepcji (który nie dotyczył problemów metod konstrukcyjnych w ich współczesnym sensie), w połowie XX wieku można było powrócić do problemów konstrukcyjnych, ale odbyło się to na innym poziomie, wzbogaconym o wykrystalizowaną w międzyczasie koncepcję algorytmu. Pojęcie to stanowi podstawę konstruktywistycznego nurtu w matematyce.
Słowo „algorytm” pochodzi od słowa „algoritmi” , które jest łacińską transliteracją nazwiska arabskiego matematyka Al-Khwarizmiego z IX wieku. Algorytm w średniowiecznej Europie to „system dziesiętno-pozycyjny i sztuka liczenia za jego pomocą”, gdyż to właśnie dzięki łacińskiemu tłumaczeniu (XII w.) traktatu Al-Khwarizmiego system pozycyjny został wprowadzony w Europie.
Struktura procesu algorytmicznego.
Proces algorytmiczny to proces kolejnych przekształceń obiektów konstrukcyjnych za pomocą dyskretnych „kroków”, z których każdy polega na zastąpieniu jednego obiektu konstrukcyjnego innym. Tak więc, gdy zastosujemy algorytm $ ™athfrak A $ do słowa $ baaba $, powstają kolejno słowa $ baaba, abaaba, baabab $ itd. Jeśli do pary liczb <307, 49 > zastosujemy, powiedzmy, algorytm kolumnowego odejmowania, to otrzymamy kolejno następujące obiekty konstrukcyjne:
$$ \begin{array}{rrrr}307 &3 \dot{0} 7 & \dot{3} \7 &. \7 &dot{0} 7 &underline{- 49 } &underline{- 49 } &underline{- 49 } &podkreślenie{- 49 } &podkreślenie{- 49 } \\{} & 8 &58 &258 \{array}$$
Zauważymy, że w serii kolejnych obiektów konstrukcyjnych, każdy kolejny obiekt konstrukcyjny jest w pełni zdeterminowany (w ramach danego algorytmu) przez obiekt konstrukcyjny bezpośrednio go poprzedzający. W bardziej rygorystycznym podejściu zakłada się też, że przejście od dowolnego obiektu konstrukcyjnego do bezpośrednio po nim następującego jest wystarczająco „elementarne” – w tym sensie, że jednoetapowa transformacja obiektu poprzedzającego w bezpośrednio po nim następujący jest lokalna (transformacji ulega nie cały obiekt konstrukcyjny, lecz tylko jego ograniczona algorytmem część; ponadto sama ta transformacja nie jest zdeterminowana przez kompletny obiekt poprzedzający, lecz tylko przez jego ograniczoną część).
Zgodnie z tym, mamy nie tylko zbiór możliwych danych wejściowych i zbiór możliwych wyników, ale także zbiór możliwych wyników pośrednich, reprezentujących środek roboczy, w którym rozwija się proces algorytmiczny. W przypadku $ \mathfrak A $ wszystkie te trzy zbiory pokrywają się, ale nie jest to prawdą w przypadku algorytmu odejmowania kolumnowego – możliwymi wejściami są pary liczb, możliwymi wynikami są liczby (wszystkie w systemie dziesiętnym), natomiast możliwymi wynikami pośrednimi są „trzypiętrowe” zapisy typu
$ \begin{array}{r} p \underline{- q } \\ r ^end{array}$
$ gdzie $ q $ to zapis liczby w systemie dziesiętnym, $ r $ to zapis podobny lub słowo puste, natomiast $ p $ to zapis liczby w systemie dziesiętnym, z kropkami nad niektórymi cyframi. Z reguły można wyróżnić kilka (nie niezależnych) parametrów charakterystycznych dla algorytmu: 1) zbiór możliwych danych wejściowych; 2) zbiór możliwych wyników; 3) zbiór możliwych wyników pośrednich; 4) regułę startu; 5) regułę bezpośredniego przejścia; 6) regułę zakończenia; oraz 7) regułę odzyskania wyniku.
Formalizacja pojęcia algorytmu.
Pojęcie algorytmu w swojej ogólnej postaci jest fundamentalnym pojęciem matematycznym, którego nie da się zdefiniować w kategoriach prostszych pojęć. Ściśle rzecz biorąc, formalizacje pojęcia algorytmu w rzeczywistości nieco je ograniczają. W każdej takiej formalizacji podana jest dokładna definicja pewnej klasy, w ramach której każdy z parametrów może się zmieniać. Poszczególne formalizacje różnią się od siebie wyborem takich klas. Ponieważ parametry jednoznacznie definiują jakiś algorytm, wybór dziedziny parametrów wyznacza pewną klasę algorytmów. Taki wybór może jednak pretendować do miana formalizacji intuicyjnego pojęcia algorytmu tylko wtedy, gdy można mieć pewność, że dla dowolnego „intuicyjnego” algorytmu istnieje równoważny algorytm w klasie algorytmów zdefiniowanych przez rozważany wybór. Wymóg ten formułuje się dla każdej formalizacji jako fundamentalną hipotezę, której przy obecnym stanie wiedzy nie da się matematycznie wykazać.
Pierwsze formalizacje tego typu zawdzięczamy E.L. Postowi
oraz A.M. Turingowi , którego konstrukcje antycypowały pod wieloma względami idee, na których opierają się współczesne komputery. Istnieją również wersje sformułowane przez A.A. Markova,
(por. algorytm normalny) oraz przez A.N. Kołmogorowa, który oparł podejście na konstrukcyjnych kompleksach topologicznych pewnego typu, co pozwala na bardziej precyzyjne wyrażenie własności „bycia lokalnym” przekształcenia. W każdej z tych formalizacji hipoteza fundamentalna jest w zadowalającej zgodności z praktyką. Innym argumentem na rzecz tej hipotezy jest fakt, że, jak można wykazać, wszystkie formalne wersje (efektywnej obliczalności), które zostały zaproponowane, są równoważne.
Jako przykład rozważmy formalizację zaproponowaną przez Turinga. W swojej pierwotnej formie był to opis pewnego teoretycznego komputera składającego się z 1) nieskończonej taśmy, podzielonej na kolejne komórki, z których każda może zawierać jakiś symbol z „alfabetu taśmy” maszyny; oraz 2) „skończonej kontroli”, która w każdym momencie czasu znajduje się w jakimś „stanie” (z danej skończonej listy stanów). Kontroler skończony może poruszać się wzdłuż taśmy, po jednej komórce na raz, i zmieniać zawartość mijanych komórek. Program, który monitoruje ruch skończonego kontrolera, stanowi algorytm obliczeń wykonywanych na takiej maszynie („algorytm Turinga” ). Dokładniejszy i bardziej szczegółowy opis znajduje się w Maszynie Turinga. Tutaj podana jest unowocześniona ekspozycja konstrukcji Turinga. Aby zdefiniować algorytm Turinga, należy określić a) parami rozłączne alfabety $ B, D, C $, z wyróżnioną literą $ lambda $ w $ D $ i wyróżnionymi literami $ alfa $ i $omega $ w $ C $; oraz b) zbiór par postaci $ ˆlangle p ˆxi , ˆeta Tq ˆrangle $ gdzie $ p, q ˆw C $, $ ˆxi , ˆeta ˆw B ˆcup D $, zaś $ T $ jest jednym z trzech symboli $ -, 0, + $; w zbiorze tym (który nazywamy programem) nie ma dwóch par o tej samej pierwszej współrzędnej. Możliwymi wejściami i możliwymi wyjściami są słowa nad $ B $, zaś możliwymi wynikami pośrednimi są słowa nad $ B $, które zawierają nie więcej niż jedną literę $ C $. Reguła startu polega na tym, że początkowe słowo $ P $ jest przekształcane na słowo $ ˆlambda ˆalpha P $. Reguła zakończenia polega na tym, że wynik pośredni, który zawiera $ ˆomega $ jest ostateczny. Reguła pobierania wyniku jest taka, że wynikiem jest sekwencja liter w końcowym wyniku pośrednim, która następuje po $ ^omega $ i poprzedza pierwszą literę nie należącą do $ B $. Reguła przekształcania, która przekształca $ A $ w $ A ^ ^prime $ jest następująca. Literę $ ^lambda $ piszemy na lewo i na prawo od $ A $; w tak powstałym słowie część postaci $ ^epsilon p ^xi $, gdzie $ p ^w C $, $ ^epsilon ^xi ^w B ^cup D $, zastępujemy słowem $ Q $ zgodnie z regułą: w programie poszukiwana jest para o pierwszym wyrazie $ p \xi $; niech drugim wyrazem tej pary będzie $ \ Tq $; jeśli $ T $ jest $ – $, to $ Q = q \epsilon \ $; jeśli $ T = 0 $, to $ Q = \epsilon q \ $; jeśli $ T $ jest $ + $, $ Q = \epsilon \eta q $. Słowo powstałe w wyniku tej zamiany to $ A ^ \prime $. For references, see , , , , , ,
of Algorithms, theory of.
Podstawowa hipoteza, o której mowa powyżej, jest zwykle nazywana tezą Churcha-Turinga lub hipotezą Turinga. Teza ta głosi, że to, co może być efektywnie obliczone zgodnie z intuicją na temat tego, co stanowi efektywny proces, może być również obliczone przez maszynę Turinga, tj. formalnie zdefiniowane pojęcie algorytmu. Z samej natury utożsamiania intuicyjnego, nieformalnego pojęcia z formalną precyzyjną definicją, teza Churcha-Turinga nie może być formalnie udowodniona.
Wiele formalizacji okazało się równoważnych, a żadna formalizacja nie okazała się ściśle mocniejsza. Poza wymienionymi wyżej formalizacjami, na Zachodzie najbardziej standardowe są następujące referencje: Churcha formalizacja liczb i funkcji obliczalnych przez wyrażenia lambda, Kleene’a ogólne schematy rekurencyjne oraz model maszyny rejestrowej zaproponowany przez J.C. Shepherdsona i H.E. Sturgisa, który został rozszerzony w bardziej realistyczny model komputera przez S.A. Cooka i R.A. Reckhowa. Wersje Markowa i Kołmogorowa są mniej znane. Dla kompletności podano również oryginalne referencje do Turinga i Posta.
| A.M. Turing, „On computable numbers, with an application to the Entscheidungsproblem” Proc. London Math.Soc. Ser. 2 , 42 (1936) s. 230-265 | |
| A.M. Turing, „Corrections to „On computable numbers, with an application to the Entscheidungsproblem” ” Proc. London Math.Soc. Ser. 2 , 43 (1937) pp. 544-546 | |
| A. Church, „An unsolvable problem of elementary number theory” Amer. J. Math. , 58 (1936) pp. 345-363 | |
| S.C. Kleene, „General recursive functions of natural numbers” Math. Ann. , 112 (1936) pp. 727-742 | |
| E.L. Post, „Formal reductions of the general combinatorial decision problem” Amer. J. Math. , 65 (1943) pp. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, „Computability of recursive functions” J. Assoc. Comp. Mach. , 10 (1963) s. 217-255 | |
| S.A. Cook, R.A. Reckhow, „Time-bounded random access machines” J. Computer and System Sciences , 7 (1973) s. 354-375 |
.