Dlaczego funkcje obliczalne nazywane są również funkcjami rekurencyjnymi?

23

W teorii obliczalności funkcje obliczeniowe nazywane są również funkcjami rekurencyjnymi. Przynajmniej na pierwszy rzut oka nie mają one nic wspólnego z tym, co nazywasz „rekurencyjnym” w codziennym programowaniu (tj. Funkcjami, które same się nazywają).

Jakie jest rzeczywiste znaczenie rekurencji w kontekście obliczalności? Dlaczego te funkcje nazywane są „rekurencyjnymi”?

Innymi słowy: jaki jest związek między dwoma znaczeniami „rekurencyjności”?

Golo Roden
źródło
2
Funkcja μ-rekurencyjna
Thomas Klimpel
3
Oszukują, ponieważ zawierają operator μ . Jest to operator minimalizacji, ale oczywiście minimalizacja ma niewiele wspólnego z rekurencją. Wygląda więc na to, że ktoś (Kleene) pomyślał, że „rekurencyjny” brzmi nieźle, więc wymyślił pretekst do używania tej nazwy. Znacznie później Robert Soare wyjaśnił, że „obliczalne” brzmiałoby znacznie lepiej, a „rekurencyjne” było po prostu marketingową sztuczką na początku i wszyscy się zgodzili.
Thomas Klimpel
3
Waht o prymitywnych funkcjach rekurencyjnych? Skopiowane z wikipedii są zdefiniowane jako i h ( S ( y ) , x 1 , , x k ) = g ( y , h ( y , x 1 , h(0,x1,,xk)=f(x1,,xk) . To funkcja, która sama się nazywa. h(S(y),x1,,xk)=g(y,h(y,x1,,xk),x1,,xk)
Hendrik Jan
3
@GoloRoden Zauważ, że opis znacznika „obliczalności” (użyłeś go do tego pytania) mówi: „teoria obliczalności aka teoria rekurencji”. Gödel nazwał funkcje rekurencyjne , ale termin przekształcił się w obliczalny . Prawdopodobnie, aby uniknąć nieporozumień takich jak twoje. Ludzie, którzy studiują teorię obliczalności (intensywnie), częściej używają terminu teoria rekurencji, aby „uszanować” swoje korzenie.
Auberon
1
ponieważ są one definiowane rekurencyjnie, tzn. „ bardziej złożone funkcje są zdefiniowane w kategoriach wcześniej zdefiniowanych, prostszych funkcji
Nikos M.

Odpowiedzi:

13

Zdefiniuj podstawowe funkcje:

  • funkcja zerowa

    zero:NN:x0
  • funkcja następcy

    sudodo:N.N.:xx+1
  • funkcja projekcji

pjan:N.nN.:(x1,x2),,xn)xja

Od teraz będę używać do oznaczenia ( x 1 , x 2 , , x n )xn¯(x1,x2),,xn)

Zdefiniuj kompozycję:

Podane funkcje

  • każdy z podpisem N kNg1,g2,,gmNkN
  • f:NmN

Skonstruuj następującą funkcję:

h:NkN:xk¯h(xk¯)=f(g1(xk¯),g2(xk¯),,gm(xk¯))

Zdefiniuj prymitywną rekurencję:

Podane funkcje

  • f:NkN
  • g:Nk+2N

Skonstruuj następującą (częściową) funkcję:

h:Nk+1N:(xk¯,y+1){f(xk¯),y+1=0g(xk¯,y,h(xk¯,y)),y+1>0

Wszystkie funkcje, które można wykonać za pomocą kompozycji i prymitywnej rekurencji na podstawowych funkcjach , nazywane są prymitywną rekurencyjną . Nazywa się to tak z definicji. Chociaż istnieje łącze z funkcjami, które same się wywołują, nie trzeba próbować łączyć ich ze sobą. Możesz uznać rekursję za homonim.

Powyższa definicja i powyższa konstrukcja została zbudowana przez Gödela (zaangażowanych było także kilka innych osób) w celu uchwycenia wszystkich obliczalnych funkcji, tj. Istnieje maszyna Turinga dla tej funkcji. Zauważ, że koncepcja maszyny Turinga nie została jeszcze opisana lub przynajmniej była niejasna.

(Nie) na szczęście przyszedł ktoś o imieniu Ackermann i zdefiniował następującą funkcję:

  • Ack:N2N
  • Ack(0,y)=y+1
  • Ack(x+1,0)=Ack(x,1)
  • Ack(x+1,y+1)=Ack(x,Ack(x+1,y))

Ack

Ack

Nieograniczona minimalizacja

  • g:NkN
  • [f(xk¯,y)=0 AND f(xk¯,z) is defined z<y AND f(xk¯,z)0]
    THEN
    g(xk¯)=y
    ELSE
    g(xk¯) is not defined.

This last one may be hard to grasp, but it basically means that g((x1,x2,,xk)) is the smallest root of f (if a root exists).


All functions that can be constructed with all the constructions defined above are called recursive. Again, the name recursive is just by definition, and it doesn't necessarily have correlation with functions that call themselves. Truly, consider it a homonym.

Recursive functions can be either partial recursive functions or total recursive functions. All partial recursive functions are total recursive functions. All primitive recursive functions are total. As an example of a partial recursive function that is not total, consider the minimisation of the successor function. The successor function doesn't have roots, so its minimisation is not defined. An example of a total recursive function (which uses minimisation) is Ack.

Now Gödel was able to construct the Ack function as well with his expanded class of functions. As a matter of fact, every function that can be computed by a Turing machine, can be represented by using the constructions above and vice versa, every construction can be represented by a Turing machine.

If you're intrigued, you could try to make Gödel's class bigger. You can try to define the 'opposite' of unbounded minimisation. That is, unbounded maximisation i.e. the function that finds the biggest root. However, you may find that computing that function is hard (impossible). You can read into the Busy Beaver Problem, which tries to apply unbounded maximisation.

Auberon
źródło
4
I know realise the given definitions don't really answer the question, but my answer describes the evolution of recursion/computability theory, kind of. Might be worth a read.
Auberon
I like it, thanks for your efforts :-)
Golo Roden
In "if h((x1,x2,...,xk),0)=f((x1,x2,...,xk))", I think you mean h((x1,x2,...,xk,0)). Also, there is no then clause prior to the next bullet point's else clause.
Eric Towers
2
Afaik, this is subtly wrong. The set if μ-recursive functions is called the set of partially recursive functions whereas recursive functions are always total. That's why the set of all total functions (resp. languages that can be decided) is called R.
Raphael
1
There are quite a few incorrect statements in your answer. You should not make up history for an answer.
Kaveh
17

The founders of computability theory were mathematicians. They founded what is now called computability theory before there was any computers. What was the way mathematicians defined functions that could be computed? By recursive definitions!

So there were recursive function before there were any other model of computation like Turing machines or lambda calculus or register machines. So people referred to these function as recursive functions. The fact that they turned out to be exactly what Turing machines and other models can compute is a later event (mostly proven by Kleene).

We have the simple definition of a recursive function which is now called primitive recursive function. There were not general enough (e.g. Ackermann's function) so people developed more general notions like μ-recursive functions and Herbrand-Gödel general recursive functions that did capture all computable functions (assuming the Church's thesis). Church claimed that his model of lambda calculus captured all computable functions. Many people, and in particular Gödel, were not convinced that these capture all functions that can be computed. Until Turing's analysis of computation and introduction of his machine model.

The name of the field used to recursion theory. However there has been a successful push in recent decades to change the name to something more appealing from recursion theory to something more computer sciency (vs. mathy). As a result the field is now called computability theory. However if you look at books, papers, conferences, etc. in the early decades they are called recursion theory and not computability theory. Even the title of Soare's own 1987 book (who was the main person behind the push to change the name to computability theory) is "Recursively Enumerable Sets and Degrees".

If you want to know more about the history a fun and good place to read about it is the first chapter of Classical Recursion Theory by Odifreddi.

Kaveh
źródło
7

Robert Soare wrote an essay about this issue. According to him, the term (general) recursive functions was coined by Gödel, who defined them using some sort of mutual recursion. The name stuck, though later on other equivalent definitions were found.

For more information, I recommend Soare's essay.

Yuval Filmus
źródło
0

zamiast długiego komentarza postanowiłem dodać odpowiedź:

Ponieważ są one definiowane rekurencyjnie , tzn. „ Bardziej złożone funkcje są zdefiniowane w kategoriach wcześniej zdefiniowanych, prostszych funkcji

Ten rodzaj procedury iteracyjnej lub przyrostowej tworzy dobrze zdefiniowane funkcje (w sensie matematycznym)

Takie jest znaczenie rekurencyjności w języku matematycznym. Zobacz poniżej, jak odnosi się to do rekurencji w języku programowania.

Porównaj tę procedurę z technikami i metodami takimi jak indukcja (matematyczna), która jest również przykładem rekurencyjności w matematyce.

Programowanie ma żyłę matematyczną i inżynierską.

Ta (zwykle konstruktywna) procedura jest również określana jako ładowanie początkowe w mowie systemów operacyjnych.

Jednak rekurencji wykonawcze z tej samej funkcji (tj caling sama podczas jego wykonywania ), gdyż musi (hmm, powinien) się zdarzyć na wartości już komputerowej (lub argumenty), czyli innymi słowy, w ramach zbioru wynikowego już obliczone , ma również charakter rekurencyjny w powyższym znaczeniu, tzn. „ zdefiniowane wcześniej zdefiniowane funkcje (i ich wartości)

W przeciwnym razie nie jest dobrze zdefiniowane i prowadzi do takich rzeczy jak przepełnienie stosu :))))

Aby podać kolejny przykład z systemów operacyjnych, rekurencja środowiska wykonawczego (wywołanie samego siebie) może być traktowana jako analogia do ponownego uruchamiania systemu operacyjnego po pewnej aktualizacji (np. Aktualizacji rdzenia). Wiele systemów operacyjnych wykonuje następującą procedurę:

  1. początkowy rozruch w celu załadowania procedur niskiego poziomu (np. I / O)
  2. wykonaj niezbędne aktualizacje (używając procedur niskiego poziomu)
  3. uruchom ponownie (efektywnie, ponownie wywołując się), ale tym razem ładując bardziej złożone procedury (lub nawet cały system)

Piękna odpowiedź Auberona bardziej szczegółowo przedstawia tego rodzaju procedurę.

Nikos M.
źródło