Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жылдам өсетін функция – математикалық функция.
Quickly growing function
the mathematical function
Есептеу теориясында Вильгельм Акерманның есімімен аталған Акерман функциясы – толық есептелетін, бірақ примитивті рекурсивті емес функциялардың ең қарапайым және ерте табылған мысалы. Барлық примитивті рекурсивті функциялар толық және есептелуге болады, бірақ Акерман функциясы барлық толық есептелетін функциялардың примитивті рекурсивті емес екенін көрсетеді. Акерман функциясы жарияланғаннан кейін (оның үш теріс емес бүтін аргументі болған), көптеген авторлар оны әртүрлі мақсаттарға бейімдеді, сондықтан қазір "Акерман функциясы" бастапқы функцияның көптеген түрінің кез келгенін білдіруі мүмкін. Ең көп тараған түрі – Роза Петер мен Рафаэль Робинсон әзірлеген екі аргументті Акерман-Петер функциясы. Оның мәні өте жылдам өседі; мысалы, нәтижесі 19 729 ондық таңбадан тұратын бүтін санды береді.
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive. After Ackermann's publication of his function (which had three non negative integer arguments), many authors modified it to suit various purposes, so that today "the Ackermann function" may refer to any of numerous variants of the original function. One common version is the two argument Ackermann–Péter function developed by Rózsa Péter and Raphael Robinson. Its value grows very rapidly; for example, results in , an integer of 19,729 decimal digits.
Есептеу
Акерманн функциясының рекурсивті анықтамасын терминдік қайта жазу жүйесіне (TRS) оңай түрде ауыстыруға болады.
The recursive definition of the Ackermann function can naturally be transposed to a term rewriting system (TRS).
Жалпы ескертулер
Бұл бағалау әрқашан аяқталады екенін бірден байқау қиын. Дегенмен, рекурсия шектеулі, себебі әр рекурсивті шақыруда немесе азаяды, немесе бірдей қалады, ал екіншісі азаяды. әр рет сайын нөлге жеткенде азаяды, сондықтан да нөлге жетеді. (Техникалық тұрғыдан алғанда, әр жағдайда жұп лексикографиялық тәртіп бойынша кемиді, бұл жақсы реттелген, дәл сол сияқты, теріс емес бүтін сандардың тәртібі; яғни, тәртіп бойынша шексіз рет кему мүмкін емес.) Бірақ, кемитін кезде қаншалықты артатынын шектеу жоқ – және ол көбінесе күрт артады. m-нің 1, 2 немесе 3 сияқты кіші мәндері үшін Аккерман функциясы n-ге қатысты салыстырмалы түрде баяу өседі (көп дегенде экспоненциалды түрде). Бірақ , ол әлдеқайда жылдам өседі; тіпті шамамен 2.00353-ке тең, ал -ның ондық кеңеюі кез келген стандартты өлшем бойынша өте үлкен, шамамен 2.12004. Қызықтысы, ол тек 1-ді қосу операциясын ғана қолданады. Оның жылдам өсуінің себебі – ұялы рекурсия. Бұл сондай-ақ оның орындалу уақыты нәтижесіне пропорционал екенін білдіреді, сондықтан ол да өте үлкен. Шындығында, көп жағдайларда орындалу уақыты нәтижеден әлдеқайда артық; жоғарыда қараңыз. Бір аргументтік нұсқасы, екі және де бірдей артады, кез келген бастапқы рекурсивті функцияны, оның ішінде экспоненциалды функция, факториал функциясы, мульти және суперфакториал функциялары сияқты өте жылдам өсетін функцияларды, тіпті Кнуттың жоғары көрсеткіш нотациясын қолданып анықталған функцияларды (индексацияланған көрсеткіш қолданылмаған жағдайларда) қарапайым етеді. Оның жылдам өсу иерархиясымен шамамен салыстыруға болады. Бұл ең жоғары өсуді, Тьюринг машинасы сияқты шексіз жады бар машинада анық есептелетін және, демек, есептелетін функция, кез келген бастапқы рекурсивті функциядан жылдам өседі және сондықтан бастапқы рекурсивті емес екенін көрсету үшін пайдалануға болады.
It may not be immediately obvious that the evaluation of always terminates. However, the recursion is bounded because in each recursive application either decreases, or remains the same and decreases. Each time that reaches zero, decreases, so eventually reaches zero as well. (Expressed more technically, in each case the pair decreases in the lexicographic order on pairs, which is a well ordering, just like the ordering of single non negative integers; this means one cannot go down in the ordering infinitely many times in succession.) However, when decreases there is no upper bound on how much can increase — and it will often increase greatly. For small values of m like 1, 2, or 3, the Ackermann function grows relatively slowly with respect to n (at most exponentially). For , however, it grows much more quickly; even is about 2.00353, and the decimal expansion of is very large by any typical measure, about 2.12004. An interesting aspect is that the only arithmetic operation it ever uses is addition of 1. Its fast growing power is based solely on nested recursion. This also implies that its running time is at least proportional to its output, and so is also extremely huge. In actuality, for most cases the running time is far larger than the output; see above. A single argument version that increases both and at the same time dwarfs every primitive recursive function, including very fast growing functions such as the exponential function, the factorial function, multi and superfactorial functions, and even functions defined using Knuth's up arrow notation (except when the indexed up arrow is used). It can be seen that is roughly comparable to in the fast growing hierarchy. This extreme growth can be exploited to show that which is obviously computable on a machine with infinite memory such as a Turing machine and so is a computable function, grows faster than any primitive recursive function and is therefore not primitive recursive.
Есептеу күрделілігі
Акерманн функциясы кейбір алгоритмдердің, мысалы, векторлық қосу жүйелері мен Петри желісінің қолжетімділігінің уақыт күрделілігінде кездеседі, осылайша олардың үлкен мысалдар үшін есептеу жүргізу қиындығын көрсетеді. Акерман функциясының керісі кейбір уақыт күрделілігі нәтижелерінде қолданылады.
The Ackermann function appears in the time complexity of some algorithms, such as vector addition systems and Petri net reachability, thus showing they are computationally infeasible for large instances. The inverse of the Ackerman function appears in some time complexity results.
Анықтама ретінде пайдалану
Акерманн функциясы, өте терең рекурсия арқылы анықталғандықтан, компилятордың рекурсияны оңтайландыру мүмкіндігін бағалау үшін өлшем ретінде қолданылуы мүмкін. Акерманн функциясы осы мақсатта алғаш рет 1970 жылы Драгош Вайда және шамамен бір уақытта 1971 жылы Ингве Сундблад тарапынан жарияланды. Сундбладтың маңызды еңбегін Брайан Вичман (Ветстон өлшемдерінің авторларының бірі) 1975 және 1982 жылдар аралығында жарық көрген үш мақалалық сериясында пайдаланды.
The Ackermann function, due to its definition in terms of extremely deep recursion, can be used as a benchmark of a compiler's ability to optimize recursion. The first published use of Ackermann's function in this way was in 1970 by Dragoș Vaida and, almost simultaneously, in 1971, by Yngve Sundblad. Sundblad's seminal paper was taken up by Brian Wichmann (co author of the Whetstone benchmark) in a trilogy of papers written between 1975 and 1982.