rekursionsteori
rekursionsteori, en huvudgren inom matematisk logik, vars centrala begrepp är rekursiv funktion, konstruerat i avsikt att precisera det intuitiva begreppet beräkningsbar funktion.
Flera av varandra oberoende konstruktioner företogs i detta syfte på 1930-talet. En tar sin utgångspunkt i ett slags abstrakt maskin, s.k. Turing-maskin (efter Alan Turing), en annan bygger på Alonzo Churchs lambdakalkyl, en tredje på s.k. Post-maskin (efter Emil Post), en fjärde, som utarbetats av Stephen Kleene på förslag av
Litteraturanvisning
Information om artikeln
Medverkande
Dag Prawitz
Källangivelse