Jump to content

Talk:Grzegorczyk hierarchy

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This page needs some cleanup. It contains factual errors (e.g. in defining the functions E_i)129.240.223.248 (talk) 17:56, 3 March 2008 (UTC)[reply]

I've corrected the definition of , and I might come back and clarify the rest of it later. Christianp (talk) 11:37, 6 August 2009 (UTC)[reply]

There's an ambiguity and possible error in the meaning of . Does the exponent denote exponentiation, or does it denote iterated application of the function? The usual meaning is of course the former, but in recursive function theory the exponent often denotes the latter. Moreover, in the definition of the fast-growing hierarchy, which is closely related, it means the latter. Either way, it deserves clarification. User:CarlFeynman 15 November 2012 —Preceding undated comment added 02:47, 16 November 2012 (UTC)[reply]

Pronunciation

[edit]

I have added a pronunciation which was verified by native speakers. If you are not good with IPA, it could be approximated by "gzhe-GOR-chik" where zh is like the s in vision. To get help with the tough gzh combination, try listening to this audio file [1] (thanks to User:Kpalion). Cheers, — sligocki (talk) 10:12, 25 October 2009 (UTC)[reply]

I usually prefer to have pronunciations on the article about the person, rather than the article about the concept. I created a stub biography for Andrzej Grzegorczyk; maybe we can move the pronunciation there. — Carl (CBM · talk) 13:15, 25 October 2009 (UTC)[reply]

Looking for reference

[edit]

There is a [citation needed] tag in Primitive_recursive_function#Relationship_to_recursive_functions about the Ackerman function. It just says that every primitive recursive function is bounded by some branch of the Ackerman function. This is obviously related to the topic here, and at hyper operation, but I have never found what I think is a good reference for the article Primitive recursive function. Does anyone here know of one? — Carl (CBM · talk) 03:36, 4 November 2009 (UTC)[reply]

Rose (1984) demonstrates that the Péter function (what is now known as the 2-argument Ackermann function) grows faster than a function which enumerates all primitive recursive functions and thus outgrows all primitive recursive functions themselves (but this book is a bit hard to find and has dated terminology). This argument was apparently originally made by Rózsa Péter in her 1935 paper. Likewise Ackermann proved his original (3-argument) function to be non-primitive recursive in his 1928 paper (but both are in German). I'd imagine there are some more recent examples that would be better to cite, but I don't know them. Cheers, — sligocki (talk) 05:26, 4 November 2009 (UTC)[reply]