Funkcja obliczalna
![]() | Ten artykuł należy dopracować: od 2017-11 → zweryfikować treść i dodać przypisy, od 2017-11 → dodać przypisy do treści niemających odnośników do źródeł, → poprawić błędy językowe lub stylistyczne (pomoc: powszechne błędy językowe), poprawiono polszczyznę i terminologię do tego momentu. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
Funkcja obliczalna – podstawowy obiekt badań teorii obliczalności. Zbiór funkcji obliczalnych jest równoważny zbiorowi funkcji obliczalnych w sensie Turinga oraz funkcji częściowo rekurencyjnych. Funkcje obliczalne są analogiczne do intuicyjnego pojęcia algorytmu. Pojęcia używa się do omawiania obliczalności bez odniesienia do określonego modelu, takiego jak maszyna Turinga, lub maszyna von Neumanna[1]. Definicja funkcji obliczalnej musi mieć odniesienie do określonego modelu obliczalności.
Z początku matematycy używali nieformalnego terminu „funkcji efektywnych”, jednak po wprowadzeniu precyzyjnej definicji funkcji obliczalnych zaczęto utożsamiać funkcje efektywne z obliczalnymi. Dla niektórych funkcji efektywnych można wykazać, że każdy algorytm będzie potrzebował czasu rosnącego wykładniczo. Teoria obliczalności i teoria złożoności zajmują się zagadnieniami obliczalności oraz złożoności obliczeń funkcji obliczalnych.
Zgodnie z hipotezą Churcha-Turinga funkcjami obliczalnymi są funkcje, które można obliczyć, używając urządzenia maszynowego oraz mając nieskończenie wiele czasu i przestrzeni pamięciowej. Hipoteza ta oznacza, że każda funkcja dająca się wyrazić przez algorytm jest obliczalna.
Aksjomaty Bluma mogą być użyte do zdefiniowania abstrakcyjnej teorii złożoności obliczeniowej na zbiorze funkcji obliczalnych. W teorii złożoności obliczeniowej problem określenia złożoności funkcji obliczalnej jest znany jako zagadnienie funkcji.
Definicja
Istnieje wiele równoważnych sposobów określenia klasy funkcji obliczalnych. Dla potrzeb tego artykułu przyjmiemy, że funkcje obliczalne zostały określone jako skończone funkcje częściowe na liczbach naturalnych, które dają się obliczyć za pomocą maszyny Turinga. Istnieje wiele równoznacznych modeli obliczalności, określających tę samą kategorię funkcji obliczalnych, takich jak:
- funkcje μ-rekurencyjne
- maszyny Turinga
- maszyny von Neumanna
- maszyny znakujące
- rachunek lambda
- programy GOTO
- programy WHILE
oraz inne.
Każda obliczalna funkcja posiada skończoną liczbę argumentów będących liczbami naturalnymi. Ponieważ funkcje te są cząstkowe, mogą one być nieokreślone dla dowolnie wybranych argumentów. Jeśli funkcja obliczalna jest określona, to jej wynikiem jest pojedyncza liczba naturalna. Takie funkcje nazywa się również funkcjami częściowo rekurencyjnymi. W teorii obliczalności jako dziedzinę funkcji przyjmuje się zbiór wszystkich argumentów, dla których dana funkcja jest określona.
Funkcję określoną dla wszystkich swoich argumentów nazywa się funkcją zupełną. Jeśli funkcja obliczalna jest zupełna, to nazywa się ją zupełną funkcją obliczalną lub zupełną funkcją rekurencyjną.
Zapis oznacza, że częściowa funkcja jest określona na argumentach a zapis oznacza, że jest określona dla argumentów i jej wartością jest
Cechy funkcji obliczalnych
Osobny artykuł: Algorytm.
Główną cechą funkcji obliczalnej jest istnienie skończonej procedury (algorytmu) określającej sposób obliczenia danej funkcji. Różne modele obliczalności dają różne interpretacje tego, czym jest taka procedura i jak jej użyć. Interpretacje te mają jednak wiele cech wspólnych. Dane modele określają równoznaczne klasy funkcji obliczalnych, gdyż każdy z tych modeli jest w stanie odczytywać i wykonywać procedury określone przez różne modele (podobnie kompilator potrafi wczytać instrukcje dla jednego języka oprogramowania i wygenerować polecenia w innym języku).
Enderton [1977] podaje następujące cechy procedury wyliczającej funkcję obliczalną. Podobne charakterystyki zostały podane przez Turinga [1936], Rogersa [1967] i innych:
- „Muszą istnieć precyzyjne polecenia (w szczególności program), skończone w długości dla danej procedury”.
Każda funkcja obliczalna musi posiadać program w pełni opisujący sposób, w który należy obliczać daną funkcję. Możliwe jest obliczenie danej funkcji poprzez ścisłe wykonywanie odpowiednich kroków w danym programie, bez zgadywania czy czerpania z dodatkowej wiedzy.
- „Jeśli do danej procedury wprowadzimy krotkę o elementach należącą do dziedziny funkcji to po skończonej liczbie kroków procedura musi zakończyć się wynikiem ”.
Procedura jest wykonywana krok po kroku, stosując określone reguły opisujące każdy krok obliczeniowy. Tylko skończona ilość kroków może zostać wykonana, nim otrzymana zostanie wartość danej funkcji.
- „Jeśli do danej procedury wprowadzimy krotkę o elementach nienależącą do dziedziny funkcji to procedura może nigdy się nie zatrzymać. Może się też zatrzymać w pewnym miejscu, nie zwracając jednak wartości funkcji dla ”.
Jeśli otrzymamy jakąś wartość dla to musi być wartość poprawna danej funkcji. Nie wymaga się od wykonującego daną procedurę, aby rozróżniał wartości wyników poprawne od niepoprawnych.
Enderton podaje kilka uściśleń, których wymagają procedury umożliwiające obliczenie wartości funkcji obliczalnych:
- Nie ma ograniczenia liczby argumentów. Nie zakłada się na przykład, że liczba argumentów jest mniejsza niż liczba atomów we wszechświecie.
- Wymaga się, aby procedura zatrzymała się po skończonej liczbie kroków, jeśli wynik ma zostać zwrócony. Liczba tych kroków może być jednak zupełnie dowolna. Nie zakłada się żadnych ograniczeń w czasie.
- Pomimo iż procedura może potrzebować jedynie skończonej ilości pamięci podczas pomyślnego obliczania wyniku, nie ma żadnego ograniczenia do co użytego miejsca. Zakłada się, że zawsze można dodać dowolną ilość dodatkowej pamięci, jeśli procedura tego wymaga.
Dziedziną badań teorii złożoności są funkcje z określonymi ograniczeniami co do czasu lub też pamięci potrzebnej do przeprowadzenia obliczeń.
Zbiory i relacje obliczalne
Podzbiór zbioru liczb naturalnych jest nazywany obliczalnym (lub też: rekurencyjnym, rozstrzygalnym), jeśli istnieje funkcja obliczalna taka, że dla każdej liczby gdy należy do i gdy nie jest elementem zbioru
Podzbiór zbioru liczb naturalnych jest nazywany obliczalnie przeliczalnym (lub też: rekurencyjnie przeliczalnym, semi-rozstrzygalnym), jeśli istnieje obliczalna funkcja taka, że dla każdej liczby jest określone wtedy i tylko wtedy, gdy jest elementem danego zbioru. Tak więc zbiór jest obliczalny przeliczalnie wtedy i tylko wtedy, gdy jest dziedziną pewnej funkcji obliczalnej.
Każda relacja skończona określona dla liczb naturalnych może zostać utożsamiona z odpowiednim zbiorem skończonych ciągów liczb naturalnych, zatem analogicznie można zdefiniować pojęcia relacji obliczalnych i relacji obliczalnych przeliczalnie.
Języki formalne
Osobny artykuł: Języki formalne.
W informatycznej teorii obliczalności powszechnie rozważa się języki formalne. Alfabetem jest dowolny zbiór. Słowem nad danym alfabetem nazywa się skończony ciąg znaków danego alfabetu, w którym ten sam znak może występować wielokrotnie. Przykładowo ciągi binarne są słowami nad alfabetem Językiem jest podzbiór zbioru wszystkich słów nad określonym alfabetem. Przykładem jest zestaw wszystkich wyrażeń zawierających dokładnie trzy jedynki nad alfabetem binarnym.
Kluczową cechą języka formalnego jest stopień trudności wymagany, aby rozstrzygnąć, czy dane słowo przynależy do danego języka. Należy stworzyć pewien system kodowania, aby umożliwić funkcji obliczalnej przyjęcie na wejście dowolnego słowa w danym języku (zwykle jest to pewien algorytm). Język nazywa się obliczalnym (lub też: rekurencyjnym, rozstrzygalnym), jeśli istnieje funkcja obliczalna taka, że dla każdego słowa w danym alfabecie gdy dane słowo jest słowem języka oraz gdy słowo nie jest słowem danego języka. Tak więc język jest obliczalny wtedy i tylko wtedy, gdy istnieje algorytm pozwalający ustalić, czy dowolne słowo należy do danego języka.
Język jest obliczalny przeliczalnie (lub też: rekurencyjnie przeliczalny, semi-rozstrzygalny), jeśli istnieje funkcja obliczalna taka, że jest określona wtedy i tylko wtedy, gdy słowo należy do danego języka. Określenie przeliczalny ma tę samą etymologię, co w przypadku obliczalnych przeliczalnie zbiorów liczb naturalnych.
Przykłady
Następujące funkcje są obliczalne:
- Każda funkcja o skończonej dziedzinie, a w szczególności każdy ciąg liczb naturalnych
- Każda funkcja stała
- Dodawanie
- Funkcja podająca czynniki pierwsze danej liczby
- Największy wspólny dzielnik dwóch liczb jest funkcją obliczalną
- Tożsamość Bézouta, liniowe równanie diofantyczne
Jeśli i są obliczalne, to również: (zakładając, że f jest funkcją jednoargumentową), oraz wiele innych kombinacji.
Poniższe przykłady są funkcjami obliczalnymi, dla których jednak nieznany jest algorytm ich obliczania:
- Funkcja taka, że gdy istnieje ciąg następujących piątek w rozwinięciu dziesiętnym i w przeciwnym przypadku jest obliczalna. (Dana funkcja jest albo stałą funkcją 1, która jest obliczalna, albo istnieje takie że dla i dla Wiemy, że każda taka funkcja musi być obliczalna – nie wiadomo jednak czy istnieją dowolnie długie ciągi następujących po sobie piątek w rozwinięciu dziesiętnym π, tak więc nie wiemy, które z tych dwóch przekształceń definicji funkcji jest poprawne, a jeżeli drugie byłoby poprawne, to ile wynosiłoby )
- Każdy skończony ciąg nieobliczalnych liczb naturalnych (jak wartości funkcji pracowitego bobra ) jest obliczalny. W szczególności dla każdej liczby naturalnej istnieje algorytm obliczający skończony ciąg – w przeciwieństwie do tego, że nie ma algorytmu obliczającego pełny ciąg tzn. dla każdego Tak więc „Drukuj 0, 1, 4, 6, 13” jest trywialnym algorytmem obliczającym Podobnie istnieje taki trywialny algorytm dla każdego danego obliczający (nawet jeśli nigdy nie będzie on nikomu znany lub przez kogokolwiek odkryty)
Hipoteza Churcha-Turinga
Osobny artykuł: Hipoteza Churcha-Turinga.
Teza Churcha głosi, że każda funkcja obliczalna poprzez procedurę posiadającą trzy własności wymienione powyżej jest funkcją obliczalną. Ponieważ te trzy właściwości nie zostały podane w sposób formalnie ścisły, twierdzenia tego nie można udowodnić. Następujące obserwacje przyjmuje się jako przesłanki prawdziwości tejże tezy:
- Jest znanych wiele równoważnych modeli obliczalności i wszystkie one zawierają równoznaczne definicje obliczalności funkcji (lub słabsze wersje w niektórych przypadkach).
- Nie podano jak dotąd żadnego ściślejszego modelu obliczalności, który zostałby ogólnie uznany za wykonalnie obliczalny.
Hipoteza Churcha-Turinga bywa czasem używana w dowodach do uzasadnienia obliczalności określonej funkcji poprzez podanie opisu procedury służącej do jej obliczenia. Jest to dopuszczalne, albowiem panuje przekonanie, iż każdy tego rodzaju opis można by uściślić poprzez mozolne podanie pełnego formalnego zapisu tego rodzaju procedury w pewnym z modeli obliczalności.
Funkcje nieobliczalne i zagadnienia nierozwiązywalne
Ponieważ każda funkcja obliczalna posiada skończoną procedurę opisującą, jak ją obliczyć, istnieje przeliczalnie wiele funkcji obliczalnych.
Niech więc oznacza skończony zbiór symboli, np. niech Następnie niech będzie zbiorem wszystkich ciągów skończonych składających się ze znaków z wraz z pustym ciągiem.
Tak więc jest nieskończonym zbiorem przeliczalnym i w naszym przykładzie mamy
Zgodnie z powyższym dowolny podzbiór jest przeliczalny, gdyż .
Zbiór wszystkich programów dla danego komputera jest podzbiorem zbioru Tak więc zbiór wszystkich programów dla danego komputera jest przeliczalny, a co za tym idzie – zbiór wszystkich funkcji obliczalnych jest przeliczalny.
Liczby rzeczywiste są nieprzeliczalne. Patrz: liczby obliczalne.
Zbiór funkcji skończonych na liczbach naturalnych jest nieprzeliczalny, tak więc ich większość jest nieobliczalna. Funkcja pracowitego bobra jest przykładem takiej funkcji.
Podobnie większość podzbiorów zbioru liczb naturalnych jest nieobliczalna. Problem stopu był pierwszym skonstruowanym zbiorem tego rodzaju. Problem rozstrzygalności, sformułowany przez Dawida Hilberta, stawia pytanie, czy istnieje efektywna procedura do określenia, które wyrażenia matematyczne (zakodowane jako liczby naturalne) są prawdziwe. Turing i Church niezależnie wykazali w roku 1930, że ten zbiór liczb naturalnych jest nieobliczalny. Zgodnie z tezą Churcha-Turinga nie istnieje efektywna procedura (z algorytmem) będąca w stanie wykonać tego rodzaju obliczenie.
Rozszerzenia obliczalności
Pojęcie obliczalności funkcji może zostać zrelatywizowane do dowolnego zbioru liczb naturalnych lub równoważnie do dowolnej funkcji odwzorowującej liczby naturalne na liczby naturalne, przy użyciu maszyny Turinga (lub dowolnego innego modelu obliczalności) rozszerzonej o wyrocznię dla lub Tego rodzaju funkcje nazywa się A-obliczalnymi lub odpowiednio f-obliczalnymi.
Pomimo iż teza Churcha-Turinga postuluje, że wszystkie funkcje obliczalne zawierają wszystkie funkcje posiadające algorytm, można rozważać również szersze klasy funkcji, pomijając postulat istnienia algorytmu. Dziedziną badań hiperobliczalności są metody i procedury mogące rozwiązać zagadnienia nierozstrzygalne algorytmicznie. Teoria hiperarytmetyki bada różnego rodzaju rozszerzenia zwykłej obliczalności. Badano również ogólne teorie rekurencji, takie jak teoria E-rekurencji, w której każdy zbiór może być argumentem funkcji E-rekurencyjnej.
Zobacz też
Przypisy
- ↑ maszyna von Neumanna [online], encyklopedia.interia.pl [dostęp 2023-09-15] (pol.).
- Britannica: topic/computable-function
- Catalana: 0268266