Primitive recursive function: Difference between revisions

Revision as of 03:58, 3 February 2025

Revision as of 07:36, 25 February 2025

Line 315:

| title=ACM '67: Proceedings of the 1967 22nd national conference

| year=1967

| pages=465–469

| doi-access=free

}}</ref> is such a language. Its computing power coincides with the primitive recursive functions. A variant of the LOOP language is [[Douglas Hofstadter]]'s [[BlooP and FlooP|BlooP]] in ''[[Gödel, Escher, Bach]]''. Adding unbounded loops (WHILE, GOTO) makes the language [[general recursive function|general recursive]] and [[Turing completeness|Turing-complete]], as are all real-world computer programming languages.

Line 351 ⟶ 352:

== References ==

* {{citation|last1=Brainerd |first1=W.S. |last2=Landweber |first2=L.H. |year=1974 |title=Theory of Computation |publisher=Wiley |isbn=0471095850}}

* {{citation|last=Hartmanis |first=Juris |author-link=Juris Hartmanis |year=1989|chapter=Overview of Computational Complexity Theory |title=Computational Complexity Theory |publisher=American Mathematical Society|pppages=1-171–17 |isbn=978-0-8218-0131-4 |series=Proceedings of Symposia in Applied Mathematics |volume=38 |mr=1020807}}

* [[Robert I. Soare]], ''Recursively Enumerable Sets and Degrees'', Springer-Verlag, 1987. {{isbn|0-387-15299-7}}

* {{citation |last=Kleene |first=Stephen Cole |author-link=Stephen Cole Kleene |year=1952|title=Introduction to Metamathematics |edition=7th [1974] reprint; 2nd |publisher=[[North-Holland Publishing Company]] |oclc=3757798 |isbn=0444100881}} Chapter XI. General Recursive Functions §57

Line 365 ⟶ 366:

| url = https://scholar.archive.org/work/ruvjr6nkyre4nfxjdme2refpwe

| volume = 2

| year = 1996}}| jstor = 420992

}}

*{{citation

| last = Severin | first = Daniel E.

Line 386 ⟶ 388:

| title = Primitive recursive functions

| volume = 53

| year = 1947| issue = 10
| doi-access = free

}}

*{{citation

Line 396 ⟶ 399:

| title = A reduction of the recursion scheme

| volume = 32

| year = 1967}}| issue = 4

| jstor = 2270177

}}

*{{citation

| last = Gladstone | first = M. D.

Line 405 ⟶ 410:

| title = Simplifications of the recursion scheme

| volume = 36

| year = 1971}}| issue = 4

| jstor = 2272468

}}

{{Mathematical logic}}