Znaczenie rekurencji w teorii obliczalności

Mówi się, że teoria obliczalności nazywana jest również teorią rekurencyjną. Dlaczego tak się nazywa? Dlaczego rekurencja ma tak duże znaczenie?

W latach dwudziestych i trzydziestych XX wieku ludzie próbowali dowiedzieć się, co to znaczy „efektywnie obliczyć funkcję” (pamiętajcie, że nie było wokół nich żadnych maszyn komputerowych ogólnego zastosowania, a komputer był dziełem ludzi).

Zaproponowano kilka definicji „obliczalnych”, z których trzy są najbardziej znane:

1. -calculus$\lambda$
2. Funkcje rekurencyjne
3. Maszyny Turinga

Okazało się, że definiują tę samą klasę funkcji teoretycznych. Ponieważ funkcje rekurencyjne są starsze niż maszyny Turinga, a nawet starszy -calculus nie został natychmiast zaakceptowany jako odpowiednie pojęcie obliczalności, przymiotnik „rekurencyjny” był szeroko stosowany (funkcje rekurencyjne, zestawy rekurencyjne, zestawy rekurencyjnie wyliczalne itp.)$\lambda$

Później spopularyzowany przez Roberta Soare'a starał się zmienić „rekurencyjny” na „obliczalny”. Dlatego obecnie mówimy o funkcjach obliczalnych i zestawach obliczalnych. Ale wiele starszych podręczników i wiele osób nadal preferuje terminologię „rekurencyjną”.

Tyle o historii. Możemy również zapytać, czy rekurencja jest ważna dla obliczeń z czysto matematycznego punktu widzenia. Odpowiedź jest bardzo jednoznaczna „tak!”. Rekurencja leży u podstaw języków programowania ogólnego zastosowania (nawet whilepętle są tylko formą rekurencji, ponieważ while p do csą takie same jak if p then (c; while p do c)), a wiele podstawowych struktur danych, takich jak listy i drzewa, jest rekurencyjnych. Rekurencja jest po prostu nieunikniona w informatyce, a szczególnie w teorii obliczeń.

Teoria obliczalności to badanie funkcji obliczalnych :-).

Takie funkcje są zwykle (w tej społeczności) definiowane jako funkcje, które można wyrazić za pomocą maszyny Turinga.

Bardziej formalnie funkcja jest obliczalna, jeśli istnieje Turing tak że jeśli wejście do wynosi wyjście wynosi$f: \mathbb{N} \mapsto \mathbb{N}$$T$$T$$x = 1^n$$T$$1^{f(x)}.$

Jak się okazuje, jeśli zdefiniujesz w ten sposób funkcje obliczeniowe (programy), są one równoważne zestawowi funkcji, które można uzyskać, stosując opisane tutaj reguły . Są one nazywane funkcjami rekurencyjnymi, ponieważ jedną z zasad uzyskiwania takich funkcji jest definicja rekurencyjna (zobacz 5. zasadę na wikipedii).

Zatem powód, dla którego teoria rekurencji ma tak duże znaczenie, jest równoważny z pytaniem, dlaczego funkcje obliczeniowe są ważne. Odpowiedź na to drugie pytanie powinna być dość oczywista :)