Teoria rekursji: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
- zdanie o intuicyjnym pojmowaniu obliczalności (patrz dyskusja) |
+ link do Hipoteza Churcha-Turinga |
||
Linia 3:
Teoria [[rekursja|rekursji]] zaczyna od badania obiektów (na przykład [[Funkcja|funkcji]], [[relacja|relacji]] czy [[zbiór|zbiorów]]), które nazywa się '''rekurencyjnymi'''. [[funkcja rekurencyjna|Funkcje rekurencyjne]] to takie funkcje o argumentach i wartościach należących do zbioru [[liczba naturalna|liczb naturalnych]], które albo są szczególnie prostej postaci (jak [[funkcja stała]] czy funkcja identycznościowa), albo powstają z tych pierwszych w wyniku zastosowania skończonej liczby "porządnych" operacji (takich jak [[składanie funkcji]] czy definiowanie rekurencyjne). Natomiast zbiór jest rekurencyjny, gdy jego [[Funkcja charakterystyczna zbioru|funkcja charakterystyczna]] jest rekurencyjna. Funkcje rekurencyjne są modelem (w sensie nieformalnym) funkcji czy relacji "obliczalnych", to znaczy takich których wartość dla dowolnych argumentów można podać w skończonej liczbie kroków w sposób mechaniczny.
Obiekty [[Rekursja|rekurencyjne]] można też zdefiniować w pozornie inny (lecz tak naprawdę równoważny) sposób. Mianowicie podzbiór '''A''' zbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istnieje [[algorytm]] rozstrzygający dla każdej liczby naturalnej czy należy ona do zbioru '''A''' czy nie. Określone w ten sposób pojęcie zbioru rekurencyjnego nie tylko jest identyczne z podanym powyżej, lecz nawet nie zależy od tego, jaki '''model obliczeń''' wybierzemy do wykonywania algorytmów. Równoważność wszystkich "sensownych" modeli obliczeń jest postulowana w
Po obiektach rekurencyjnych następny stopień złożoności prezentują obiekty '''rekurencyjnie przeliczalne'''. Jeśli relacja '''R'''(m(1),...,m(k),n(1),...,n(l)) jest rekurencyjna, to relacja "istnieją takie m(1),...,m(k), że '''R'''(m(1),...,m(k),n(1),...,n(l))" jest rekurencyjnie przeliczalna. Dodając w definicji relacji kolejne kwantyfikatory ogólne i egzystencjalne w sposób naprzemienny, uzyskujemy nowe relacje, które mają (a w każdym razie mogą mieć) coraz większy stopień złożoności. W ten sposób powstaje cała hierarchia obiektów, nazywana '''hierarchią arytmetyczną''', której "piętra" można ponumerować liczbami naturalnymi.
| |||