|
Grzegorczyk Hierarchy
The Grzegorczyk hierarchy (, ), named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory. Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level. The hierarchy deals with the rate at which the values of the functions grow; intuitively, functions in lower levels of the hierarchy grow slower than functions in the higher levels. Definition First we introduce an infinite set of functions, denoted ''Ei'' for some natural number ''i''. We define : \begin E_0(x,y) & = & x + y \\ E_1(x) & = & x^2 + 2 \\ E_(0) & = & 2 \\ E_(x+1) & = & E_(E_(x)) \\ \end E_0 is the addition function, and E_1 is a unary function which squares its argument and adds two. Then, for each ''n'' greater than 1, E_n(x)=E^_(2), i.e. the ''x''-th iterate of E_ evaluated at 2. From these functions we define the Grzegorczyk hierarchy. \mathcal^n, the ''n''- ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Andrzej Grzegorczyk
Andrzej Grzegorczyk (; 22 August 1922 – 20 March 2014) was a Polish logician, mathematician, philosopher and ethicist. He was noted for his work in computability, mathematical logic and the foundations of mathematics. Family In 1953, Grzegorczyk married Renata Maria Grzegorczykowa, a Polish philologist and expert in polonist linguistics. They had a daughter and a son. Grzegorczyk died of natural causes in Warsaw on 20 March 2014 at the age of 91. His body is buried in the Cemetery of Pruszków. See also * List of Polish people Sources *Odintsov, Sergei Pavlovich (2018)Larisa Maksimova on Implication, Interpolation, and Definability Springer International Publishing, Cham *Golińska-Pilarek, Joanna; Huuskonen, Taneli (2017): ''Grzegorczyk's non-Fregean logics and their formal properties''. In Urbaniak, Rafał; Payette, Gillman (editors) (2017): Applications of Formal Philosophy: The Road Less Travelled'. Springer International Publishing, Cham, Chapter 12, pp. 24 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |