Кіріспе
Компьютерлік күрделілік теориясында элементар рекурсивті функциялардың күрделілік класы ЭЛЕМЕНТАРЛЫҚ – бұл кластардың бірігісі. Бұл атауды Ласло Кальмар рекурсивті функциялар және шешілмейтін мәселелер контекстінде берген; оның көптеген мәселелері элементарлықтан қалыс. Кейбір табиғи рекурсивті мәселелер ЭЛЕМЕНТАРЛЫҚ класына кірмейді, демек ЭЛЕМЕНТАРЛЫҚ емес. Ең қызығы, ЭЛЕМЕНТАРЛЫҚ класына жатпайтын примитивті рекурсивті мәселелер бар. Біз мынадай қатынасты білеміз:
The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know
LOWER ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R
Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.
ТӨМЕНГІ ЭЛЕМЕНТАРЛЫҚ ⊊ EXPTIME ⊊ ЭЛЕМЕНТАРЛЫҚ ⊊ PR ⊊ R
The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know
LOWER ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R
Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.
ЭЛЕМЕНТАРЛЫҚ шектелген экспоненциацияны қамтиды (мысалы, ), ал PR элементтікке кірмейтін, жалпы гипер операторларды (мысалы, тетрация) пайдалануға рұқсат береді.
The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know
LOWER ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R
Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.
Анықтама
Элементар рекурсивті функциялардың анықтамасы примитивті рекурсивті функцияларға ұқсас, бірақ примитивті рекурсияның орнына шектелген қосынды және шектелген көбейтінді қолданылады. Барлық функциялар натурал сандармен жұмыс істейді. Негізгі функциялар, олардың барлығы элементар рекурсивті: нөлдік функция. 0-ді қайтарады: f(x) = 0. Ілеспе функция: f(x) = x + 1. Көбінесе бұл S арқылы, яғни S(x) деп белгіленеді. Ілеспе функцияны қайталап қолдану арқылы қосуға қол жеткізуге болады. Проекция функциялары: олар аргументтерді назарға алмау үшін қолданылады. Мысалы, f(a, b) = a – проекция функциясы. Азайту функциясы: f(x, y) = x − y, егер y < x болса, немесе 0, егер y ≥ x болса. Бұл функция шарттарды және итерацияны анықтау үшін қолданылады. Осы негізгі функциялардан басқа элементар рекурсивті функцияларды құрастыруға болады. Композиция: кейбір элементар рекурсивті функцияның мәнін басқа элементар рекурсивті функцияға аргумент ретінде қолдану. f(x1, ..., xn) = h(g1(x1, ..., xn), ..., gm(x1, ..., xn)) элементар рекурсивті болады, егер h элементар рекурсивті болса және әрбір gi элементар рекурсивті болса. Шектелген қосынды: егер g элементар рекурсивті болса, онда ол элементар рекурсивті болады. Шектелген көбейтінді: егер g элементар рекурсивті болса, онда ол элементар рекурсивті болады.
Zero function. Returns zero: f(x) = 0. Successor function: f(x) = x + 1. Often this is denoted by S, as in S(x). Via repeated application of a successor function, one can achieve addition. Projection functions: these are used for ignoring arguments. For example, f(a, b) = a is a projection function. Subtraction function: f(x, y) = x − y if y < x, or 0 if y ≥ x. This function is used to define conditionals and iteration. From these basic functions, we can build other elementary recursive functions. Composition: applying values from some elementary recursive function as an argument to another elementary recursive function. In f(x1, , xn) = h(g1(x1, , xn), , gm(x1, , xn)) is elementary recursive if h is elementary recursive and each gi is elementary recursive. Bounded summation: is elementary recursive if g is elementary recursive. Bounded product: is elementary recursive if g is elementary recursive.
ЕНІСТІКТІК негіз
Элементарлық функциялар класы проекциялардың композициясы бойынша жабылумен және келесі функциялар жиындарының бірімен сәйкес келеді: , , , мұнда – жоғарыда анықталған азайту функциясы.
Төменгі элементтік рекурсивті функциялар
Төменгі элементар рекурсивті функциялар жоғарыда көрсетілген анықтамалар бойынша келеді, бірақ шектелген көбейтуге рұқсат етілмейді. Яғни, төменгі элементар рекурсивті функция нөл, ізбасар немесе проекция функциясы болуы керек, немесе басқа төменгі элементар рекурсивті функциялардың композициясы, немесе басқа төменгі элементар рекурсивті функцияның шектелген қосындысы. Төменгі элементар рекурсивті функциялар Сколем элементар функциялары деп те аталады. Элементар рекурсивті функциялар потенциалды түрде экспоненциалды өсімнен артық болуы мүмкін, ал төменгі элементар рекурсивті функциялар полиномиалды өсімге ие. Төменгі элементар функциялар класы элементар функциялар үшін болғандай, қарапайым функциялардың композициясы тұрғысынан сипатталады. Атап айтқанда, полиномиалдық шектелген функция төменгі элементар болып табылады, егер және тек қана оны келесі функциялардың композициясын қолдану арқылы өрнектеуге болады: проекциялар, , , , , , бір экспоненциалдық функция (немесе) формулалардың құрылымына келесі шектеу қойылады: формула экспонентаға қатысты екі қабаттан аспауы керек (мысалы, 1 қабатты, 2 қабатты, 3 қабатты). Мұнда – n және m-нің біттік АНД (ЖӘНЕ).
Сипаттамалық сипаттама
Суреттемелік күрделілікте ELEMENTARY, жоғары дәрежелі логика формуласымен сипатталатын тілдердің HO класына тең. Бұл, ELEMENTARY күрделілік класындағы әрбір тіл, тілдегі элементтер үшін ғана дұрыс болатын жоғары реттік формулаға сәйкес келеді дегенді білдіреді. Нақтырақ айтқанда, , мұнда ⋯ i дәрежелі экспоненциация мұнарасын білдіреді, ал – i-ші реттік экзистенциалдық квантификаторлармен басталып, содан кейін (i-1)-ші реттік формуладан тұратын сұранымдар класы.