Täisrekursiivne funktsioon

Matemaatilises loogikas ja arvutiteaduses on üldine rekursiivne funktsioon, osaline rekursiivne funktsioon või μ-rekursiivne funktsioon naturaalarvudest naturaalarvudeni osaline funktsioon, mis on "arvutatav" nii intuitiivses kui ka formaalses mõttes.

Kui funktsioon on totaalne, nimetatakse seda ka totaalseks rekursiivseks funktsiooniks või täisrekursiivne funktsiooniks (mõnikord lühendatakse seda rekursiivseks funktsiooniks).^[1] Arvutavuse teoorias on näidatud, et μ-rekursiivsed funktsioonid on just need funktsioonid, mida saab arvutada Turingi masinatega^[2]^[3] (see on üks Church-Turingi teesi toetavatest teoreemidest). μ-rekursiivsed funktsioonid on tihedalt seotud primitiivsete rekursiivsete funktsioonidega ja nende induktiivne määratlus põhineb primitiivsete rekursiivsete funktsioonide omal. Kuid mitte iga täielik rekursiivne funktsioon ei ole primitiivne rekursiivne funktsioon – kuulsaim näide on Ackermanni funktsioon.

Definitsioon: muuda

μ-rekursiivsed funktsioonid (või üldised rekursiivsed funktsioonid) on osafunktsioonid, mis võtavad naturaalarvude lõplikke ennikuid ja tagastavad ühe naturaalarvu. Need on väikseim osafunktsioonide klass, mis sisaldab algfunktsioone ja on suletud kompositsiooni, primitiivse rekursiooni ja minimeerimisoperaatori μ all.^[4]

↑ "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.
↑ Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."
↑ Turing, Alan Mathison (Dec 1937). "Computability and λ-Definability".
↑ Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972

^[1] ^[2] ^[3] ^[4] ^[5]

↑ "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.
↑ Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."
↑ Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.
↑ Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972
↑ https://en.wikipedia.org/wiki/General_recursive_function#cite_note-Enderton.1972-5

[1] "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.

[2] Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."

[3] Turing, Alan Mathison (Dec 1937). "Computability and λ-Definability".

[4] Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972

[5] "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.

[6] Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."

[7] Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.

[8] Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972

[9] ttps://en.wikipedia.org/wiki/General_recursive_function#cite_note-Enderton.1972-5

[1]

[2]

[3]

[4]

[1]

[2]

[3]

[4]

[5]