Teoria rekursji: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m r2.5.2) (robot poprawia: uk:Теорія обчислень |
- zdanie o intuicyjnym pojmowaniu obliczalności (patrz dyskusja) |
||
Linia 1:
'''Teoria rekursji''' to dział [[Logika matematyczna|logiki matematycznej]], którego początki sięgają [[Lata 30. XX wieku|lat trzydziestych XX wieku]]. Do jego powstania i rozwoju w znacznym stopniu przyczynili się między innymi [[Alan Mathison Turing|Alan Turing]] i [[Stephen Cole Kleene]].
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 '''tezie Churcha''', według której to czy zbiór (funkcja, relacja) jest obliczalny czy też nie, nie zależy od wyboru modelu obliczeń.
| |||