Ackermann function (original) (raw)

About DBpedia

Ackermannova funkce je příkladem funkce, která je rekurzivní a přitom není primitivně rekurzivní. Hodnota Ackermannovy funkce roste velmi rychle a už pro velmi malá čísla (4, 5, …) je nemyslitelné tuto hodnotu spočítat. Např. A(4) je tak obrovské číslo, že už počet jeho číslic je vyšší než počet všech atomů v pozorovaném vesmíru. Jinak řečeno, Ackermannova funkce roste nade všechny rozumně představitelné meze a není omezitelná žádnou běžně používanou funkcí.

Property Value
dbo:abstract Ackermannova funkce je příkladem funkce, která je rekurzivní a přitom není primitivně rekurzivní. Hodnota Ackermannovy funkce roste velmi rychle a už pro velmi malá čísla (4, 5, …) je nemyslitelné tuto hodnotu spočítat. Např. A(4) je tak obrovské číslo, že už počet jeho číslic je vyšší než počet všech atomů v pozorovaném vesmíru. Jinak řečeno, Ackermannova funkce roste nade všechny rozumně představitelné meze a není omezitelná žádnou běžně používanou funkcí. (cs) En teoria de la computació, la funció d'Ackermann és una funció recursiva que pren dos nombres naturals com arguments i retorna un únic nombre natural. Com a norma general es defineix com segueix: Ara bé, a efectes pedagògics es pot utilitzar una versió alternativa: On és la funció successora i és la funció potència (aquella que aplica f vegades). (ca) في نظرية الحوسبة، دالة أكرمان، والتي سميت من بعد الرياضي الألماني فيلهلم أكرمان, و هي من أحدث الامثلة المكتشفة على الدوال الحسابية التي ليست . جميع الدوال البدائية العودية كاملة وقابلة للحساب، ولكن دالة أكرمان توضح أنه ليست كل الدوال الكلية القابلة للحساب بدائية عودية. بعد نشر أكرمان لدالته (التي كانت لها ثلاث متغيرات صحيحة موجبة)، عدلها العديد من المؤلفين من بعده لتتناسب مع أغراضهم المختلفة، قد تشير «دالة أكرمان» إلى أي من الاشكال المختلفة للدالة الاصلية. واحدة من هاته الدوال وهي نسخة مشتركة فيما بينهم. وهي دالة أكرمان - بيتر ذات المتغيرين, وهي معرفة كما يلي: قيمة هذه الدالة تتزايد بشكل كبير جدا حتى من اجل قيم متغيرات صغيرة، فمثلا A(4,2) عدد صحيح متكون من 19,729 رقم عشري. (ar) 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, the two-argument Ackermann–Péter function is defined as follows for nonnegative integers m and n: Its value grows rapidly, even for small inputs. For example, A(4, 2) is an integer of 19,729 decimal digits (equivalent to 265536−3, or 22222−3). (en) Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen aufgezeigt werden können. Heute gibt es eine ganze Reihe von Funktionen, die als Ackermannfunktion bezeichnet werden. Diese weisen alle ein ähnliches Bildungsgesetz wie die ursprüngliche Ackermannfunktion auf und haben auch ein ähnliches Wachstumsverhalten. (de) En matematiko, akermana funkcio aŭ funkcio de Ackermann-Péter estas funkcio A(m,n) kiu prenas du naturajn nombrojn kiel argumentoj kaj redonas naturan nombron. Vidu artikolon Wilhelm Ackermann. (eo) En teoría de la computación, una función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann. Tiene un crecimiento extremadamente rápido, lo que es de interés para la ciencia computacional teórica y la teoría de la computabilidad. Hoy en día hay una serie de funciones que son llamadas funciones de Ackermann. Todas ellas tienen una forma similar a la ley original la función de Ackermann y también tienen un comportamiento de crecimiento similar. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue: (es) Dans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la forme qu'en a proposée la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(m, n). (fr) アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数 m と n に対し、 によって定義される関数のことである。 与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。 また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを（再帰呼出しのない手続き型の）プログラミング言語の言葉で言えば、アッカーマン数をプログラムで計算することはできるが、While文を使わずFor文のみでそれを計算することができない、ということになる。 (ja) In de berekenbaarheidstheorie is de ackermannfunctie, genoemd naar Wilhelm Ackermann, die de functie in 1926 opstelde, een van de eenvoudigste en vroegst ontdekte voorbeelden van een totale berekenbare functie die niet primitief recursief is. Alle primitieve recursieve functies zijn totaal en berekenbaar, maar de ackermannfunctie illustreert dat niet alle totale berekenbare functies primitief recursief zijn. De ackermannfunctie is een extreem snel toenemende functie met behulp waarvan de grenzen aan computer- en rekenmodellen in de theoretische informatica kunnen worden aangetoond. Na Ackermanns publicatie van de functie (die drie natuurlijke getallen als argumenten had), hebben veel auteurs het concept aangepast voor verschillende doeleinden, zodat tegenwoordig "ackermannfunctie" kan verwijzen naar een van de vele varianten van de oorspronkelijke door Ackermann opgestelde functie. Deze hebben alle een vormingsregel vergelijkbaar met de oorspronkelijke ackermannfunctie en hebben ook een vergelijkbaar groeigedrag. Een veelgebruikte versie, de ackermann-péterfunctie, heeft twee argumenten en is hieronder gedefinieerd. (nl) 계산 가능성 이론에서, 빌헬름 아커만의 이름을 딴 아커만 함수(Ackermann函數, 영어: Ackermann function)는 원시 재귀 함수가 아닌 전역적인 재귀 함수(계산가능 함수)의 가장 간단한 예시로, 가장 먼저 발견된 것이기도 하다. 모든 원시 재귀 함수는 완전히 정의되고 계산 가능하지만 아커만 함수는 모든 전역적 재귀 함수가 원시 재귀 함수일 필요는 없다는 것을 보였다. 음이 아닌 정수 세 개를 변수로 가지는 아커만 함수에 대한 아커만의 출간물 이후 많은 저자들은 다양한 목적에 따라서 이 함수를 수정하였다. 따라서 오늘날 "아커만 함수"라고 하면 오리지날 함수의 수많은 변형 중 하나를 의미하는 것이다. 일반적인 변형의 일종으로서, 변수가 두 개인 아커만-페테르 함수(영어: Ackermann–Péter function)는 음이 아닌 정수 m과 n에 대해 다음과 같이 정의된다. 이 값은 입력이 작더라도 매우 빠르게 증가한다. 예를 들면, A(4,2)는 265536-3으로서, 19,729자리의 정수이다. (ko) In matematica, la funzione di Ackermann è una funzione che ha come dominio l'insieme delle terne di numeri naturali e come codominio i numeri naturali. Essa è definita per ricorrenza nel seguente modo: Un caso particolare è la funzione di Ackermann a due argomenti , così definita: La funzione di Ackermann è un esempio di funzione ricorsiva che non è primitiva ricorsiva poiché cresce più velocemente di qualsiasi funzione ricorsiva primitiva. Il valore cresce molto rapidamente anche per valori molto piccoli di e . Per esempio, è un numero intero di 19 729 cifre. Per confronto, la costante di Avogadro ha solo 24 cifre. Il meccanismo di calcolo della funzione è estremamente semplice, quanto pesante dal punto di vista computazionale. La definizione data può essere vista come quella di una famiglia di funzioni al variare di un parametro individuato dalla prima variabile. Per ogni valore del parametro si ha una funzione che è ottenuta iterando la funzione precedente per un numero di volte individuato dalla seconda variabile. In quest'ottica le prime funzioni della famiglia sono funzioni familiari come l'addizione, la moltiplicazione e la potenza, seguite dalla tetrazione, e successivamente si hanno funzioni sempre più complesse: (mediante iterazione di per volte) (mediante iterazione di per volte) ( volte)(mediante iterazione di per volte e quindi mediante iterazione di e quindi mediante iterazione di ) Risulta quindi una funzione con una complessità estremamente elevata anche per valori di input semplici. L'inversa della funzione di Ackermann, indicata con oppure , compare in alcune dimostrazioni di scienze informatiche, come nell'algoritmo union-find. (it) Na teoria da computabilidade, a Função de Ackermann, nomeada por Wilhelm Ackermann, é um dos mais simples e recém-descobertos exemplos de uma função computável que não são funções recursivas primitivas. Todas as funções recursivas primitivas são totais e computáveis, mas a Função de Ackermann mostra que nem toda função total-computável é recursiva primitiva. Depois que Ackermann publicou sua função (que continha três inteiros positivos como argumentos), vários autores a modificaram para atender a várias finalidades. Então, a função de Ackermann atual pode ser referenciada a uma de suas várias formas da função original. Uma das versões mais comuns, a função de Ackermann-Péter (com dois argumentos), é definida a seguir para os inteiros não negativos m e n: Como se pode ver, seu valor cresce rapidamente, até mesmo para pequenas entradas. Por exemplo, A(4,2) resulta em um inteiro com 19.729 dígitos. (pt) Funkcja Ackermanna – funkcja matematyczna odkryta przez Wilhelma Ackermanna w 1928 roku. Cechą charakterystyczną tej dwuargumentowej funkcji jest jej nadzwyczaj szybki wzrost. Funkcja Ackermanna jest prostym przykładem funkcji rekurencyjnej, niebędącej funkcją pierwotnie rekurencyjną. Funkcje pierwotnie rekurencyjne to większość znanych funkcji, między innymi dodawanie, funkcja wykładnicza itp. Funkcja Ackermanna często jest używana do testowania jakości optymalizacji kompilatorów – stosunki czasu wykonania pomiędzy różnymi kompilatorami tego samego języka czasami sięgają tysiąca. Jakość kodu generowana dla tego typu funkcji jest szczególnie ważna w językach funkcyjnych, gdzie używa się rekursji. Inną funkcją o własnościach podobnych do funkcji Ackermanna (tzn. będąca rekurencyjną i nie pierwotnie rekurencyjną) jest funkcja Sudana. (pl) Ackermannfunktionen är ett exempel på en beräkningsbar funktion som inte är primitivt rekursiv. Ackermannfunktionen definieras för icke-negativa heltal och enligt: Från definitionen syns tydligt att för växer väldigt snabbt, redan för låga värden på n. Exempelvis är skrivet i decimal form ett heltal med över 19 000 siffror. För specifika värden på , då kan beskrivas med relativt enkla medel: För större värden på växer funktionen alltför snabbt för att beskrivas med några av de elementära räknesätten. I stället kan Knuths pilnotation användas. Generellt gäller att Med hjälp av denna beskrivning kan rekursionen av göras något enklare. Och då förstås att detta tal utskrivet i decimal form har 19 729 siffror. (sv) Функція Акермана — у теорії складності обчислень є найпростішим прикладом обчислюваної функції, що не є примітивно-рекурсивною. Функція Акермана визначається рекурсивно для невід'ємних цілих чисел та таким чином: Рекурсія завжди закінчується, оскільки або зменшується значення , або значення зберігається, а зменшується значення . Тобто пара завжди зменшується з точки зору лексикографічного порядку. Функція зростає дуже швидко (значно швидше за експоненту). Наприклад, , що перевищує кількість атомів у видимому Всесвіті. (uk) Функция Аккермана — всюду определённая вычислимая функция, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается . Эта функция растёт очень быстро, например, число настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной. В теоретической информатике она применяется для демонстрации пределов возможностей компьютеров и методов оптимизации. Также существует целое семейство родственных ей функций, имеющих схожую скорость роста и схожее определение. (ru) 阿克曼函數是非原始递归函数的例子；它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高。 (zh)
dbo:wikiPageExternalLink http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf http://forum.wolframscience.com/showthread.php%3Fs=&threadid=579 http://gdz.sub.uni-goettingen.de/en/dms/loader/img/%3FPPN=PPN235181684_0099&DMDID=DMDLOG_0009 http://timkoop.com/koop_loop_ackermanns_function_as_a_for_loop http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm http://www.dcc.fc.up.pt/~acm/PRinv.pdf http://www.gfredericks.com/main/sandbox/arith/ackermann http://www.mrob.com/pub/math/ln-2deep.html https://msp.org/pjm/1965/15-3/p25.xhtml https://research.tue.nl/files/4245011/398270.pdf https://www.dcc.fc.up.pt/~acm/ack.pdf http://www.scottaaronson.com/writings/bignumbers.html http://www.mrob.com/pub/math/largenum-3.html http://www.mrob.com/pub/math/largenum.html http://rosettacode.org/wiki/Ackermann_Function http://www.geocities.com/hjsmithh/Ackerman/index.html https://books.google.com/books%3Fid=rUudIPZD-B0C&pg=PA61 https://ghostarchive.org/archive/20221009/http:/history.dcs.ed.ac.uk/archive/docs/Imp_Benchmarks/acklt.pdf https://ghostarchive.org/archive/20221009/http:/www.dcc.fc.up.pt/~acm/PRinv.pdf https://ghostarchive.org/archive/20221009/https:/research.tue.nl/files/4245011/398270.pdf https://ghostarchive.org/archive/20221009/https:/www.dcc.fc.up.pt/~acm/ack.pdf https://web.archive.org/web/20070821224819/http:/yucs.org/~gnivasch/alpha/index.html https://web.archive.org/web/20091026171012/http:/www.geocities.com/hjsmithh/Ackerman/index.html https://www.researchgate.net/publication/351063906 http://projecteuclid.org/DPubS%3Fverb=Display&version=1.0&service=UI&handle=euclid.bams/1183512393&page=record http://history.dcs.ed.ac.uk/archive/docs/Imp_Benchmarks/acklt.pdf
dbo:wikiPageID 2925 (xsd:integer)
dbo:wikiPageLength 50758 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1123526697 (xsd:integer)
dbo:wikiPageWikiLink dbr:Primitive_recursive_function dbr:Rosetta_Code dbr:Scott_Aaronson dbr:Memoization dbr:Bernard_Chazelle dbr:David_Hilbert dbr:Algorithm dbr:Hyperoperation dbr:Reuben_Goodstein dbr:Double_recursion dbc:Large_integers dbr:Compiler dbr:Computability_theory dbr:Computable_function dbr:Rewriting dbr:Function_composition dbr:Multiplication dbr:Lexicographic_order dbr:Stack_(abstract_data_type) dbr:Computational_complexity_theory dbr:Mathematische_Annalen dbr:Phi dbr:Sudan_function dbr:Ceiling_function dbr:Total_function dbr:Well-order dbr:Wilhelm_Ackermann dbr:Gabriel_Sudan dbr:Addition dbr:American_Mathematical_Monthly dbc:Arithmetic dbr:Exponential_function dbr:Exponentiation dbr:Floor_function dbr:Fast-growing_hierarchy dbr:Graham's_number dbr:Knuth's_up-arrow_notation dbr:Recursion dbr:Goodstein_function dbr:Inverse_function dbr:Iterated_function dbr:ACM_SIGACT dbc:Computability_theory dbc:Special_functions dbc:Theory_of_computation dbr:Superfactorial dbr:Whetstone_(benchmark) dbr:Disjoint-set_data_structure dbr:BIT_Numerical_Mathematics dbr:Bulletin_of_the_American_Mathematical_Society dbr:Theoretical_Computer_Science dbr:Minimum_spanning_tree dbr:Associative dbr:Recursion_(computer_science) dbr:Reduction_strategy dbr:Turing_machine dbr:Rózsa_Péter dbr:Exponential_growth dbr:Pseudocode dbr:Pacific_Journal_of_Mathematics dbr:Robert_Creighton_Buck dbr:Raphael_Robinson
dbp:id p/a120110 (en)
dbp:mode cs1 (en)
dbp:title Ackermann function (en)
dbp:urlname AckermannFunction (en)
dbp:wikiPageUsesTemplate dbt:Springer dbt:About dbt:Authority_control dbt:Citation dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Cite_report dbt:Cite_web dbt:DADS dbt:E dbt:Harvtxt dbt:I_sup dbt:Large_numbers dbt:MathWorld dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Short_description dbt:Space dbt:Diagonal_split_header dbt:Use_shortened_footnotes dbt:Hyperoperations
dct:subject dbc:Large_integers dbc:Arithmetic dbc:Computability_theory dbc:Special_functions dbc:Theory_of_computation
rdf:type owl:Thing yago:WikicatArithmeticFunctions yago:WikicatLargeIntegers yago:WikicatLargeNumbers yago:WikicatSpecialFunctions yago:Abstraction100002137 yago:Battalion113775093 yago:DefiniteQuantity113576101 yago:Function113783816 yago:IndefiniteQuantity113576355 yago:Integer113728499 yago:LargeIndefiniteQuantity113757724 yago:LargeInteger113745420 yago:MathematicalRelation113783581 yago:Measure100033615 yago:Number113582013 yago:Relation100031921 yago:WikicatFunctionsAndMappings yago:WikicatElementarySpecialFunctions
rdfs:comment Ackermannova funkce je příkladem funkce, která je rekurzivní a přitom není primitivně rekurzivní. Hodnota Ackermannovy funkce roste velmi rychle a už pro velmi malá čísla (4, 5, …) je nemyslitelné tuto hodnotu spočítat. Např. A(4) je tak obrovské číslo, že už počet jeho číslic je vyšší než počet všech atomů v pozorovaném vesmíru. Jinak řečeno, Ackermannova funkce roste nade všechny rozumně představitelné meze a není omezitelná žádnou běžně používanou funkcí. (cs) En teoria de la computació, la funció d'Ackermann és una funció recursiva que pren dos nombres naturals com arguments i retorna un únic nombre natural. Com a norma general es defineix com segueix: Ara bé, a efectes pedagògics es pot utilitzar una versió alternativa: On és la funció successora i és la funció potència (aquella que aplica f vegades). (ca) Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen aufgezeigt werden können. Heute gibt es eine ganze Reihe von Funktionen, die als Ackermannfunktion bezeichnet werden. Diese weisen alle ein ähnliches Bildungsgesetz wie die ursprüngliche Ackermannfunktion auf und haben auch ein ähnliches Wachstumsverhalten. (de) En matematiko, akermana funkcio aŭ funkcio de Ackermann-Péter estas funkcio A(m,n) kiu prenas du naturajn nombrojn kiel argumentoj kaj redonas naturan nombron. Vidu artikolon Wilhelm Ackermann. (eo) En teoría de la computación, una función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann. Tiene un crecimiento extremadamente rápido, lo que es de interés para la ciencia computacional teórica y la teoría de la computabilidad. Hoy en día hay una serie de funciones que son llamadas funciones de Ackermann. Todas ellas tienen una forma similar a la ley original la función de Ackermann y también tienen un comportamiento de crecimiento similar. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue: (es) Dans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la forme qu'en a proposée la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(m, n). (fr) アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数 m と n に対し、 によって定義される関数のことである。 与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。 また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを（再帰呼出しのない手続き型の）プログラミング言語の言葉で言えば、アッカーマン数をプログラムで計算することはできるが、While文を使わずFor文のみでそれを計算することができない、ということになる。 (ja) 계산 가능성 이론에서, 빌헬름 아커만의 이름을 딴 아커만 함수(Ackermann函數, 영어: Ackermann function)는 원시 재귀 함수가 아닌 전역적인 재귀 함수(계산가능 함수)의 가장 간단한 예시로, 가장 먼저 발견된 것이기도 하다. 모든 원시 재귀 함수는 완전히 정의되고 계산 가능하지만 아커만 함수는 모든 전역적 재귀 함수가 원시 재귀 함수일 필요는 없다는 것을 보였다. 음이 아닌 정수 세 개를 변수로 가지는 아커만 함수에 대한 아커만의 출간물 이후 많은 저자들은 다양한 목적에 따라서 이 함수를 수정하였다. 따라서 오늘날 "아커만 함수"라고 하면 오리지날 함수의 수많은 변형 중 하나를 의미하는 것이다. 일반적인 변형의 일종으로서, 변수가 두 개인 아커만-페테르 함수(영어: Ackermann–Péter function)는 음이 아닌 정수 m과 n에 대해 다음과 같이 정의된다. 이 값은 입력이 작더라도 매우 빠르게 증가한다. 예를 들면, A(4,2)는 265536-3으로서, 19,729자리의 정수이다. (ko) Функція Акермана — у теорії складності обчислень є найпростішим прикладом обчислюваної функції, що не є примітивно-рекурсивною. Функція Акермана визначається рекурсивно для невід'ємних цілих чисел та таким чином: Рекурсія завжди закінчується, оскільки або зменшується значення , або значення зберігається, а зменшується значення . Тобто пара завжди зменшується з точки зору лексикографічного порядку. Функція зростає дуже швидко (значно швидше за експоненту). Наприклад, , що перевищує кількість атомів у видимому Всесвіті. (uk) Функция Аккермана — всюду определённая вычислимая функция, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается . Эта функция растёт очень быстро, например, число настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной. В теоретической информатике она применяется для демонстрации пределов возможностей компьютеров и методов оптимизации. Также существует целое семейство родственных ей функций, имеющих схожую скорость роста и схожее определение. (ru) 阿克曼函數是非原始递归函数的例子；它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高。 (zh) في نظرية الحوسبة، دالة أكرمان، والتي سميت من بعد الرياضي الألماني فيلهلم أكرمان, و هي من أحدث الامثلة المكتشفة على الدوال الحسابية التي ليست . جميع الدوال البدائية العودية كاملة وقابلة للحساب، ولكن دالة أكرمان توضح أنه ليست كل الدوال الكلية القابلة للحساب بدائية عودية. بعد نشر أكرمان لدالته (التي كانت لها ثلاث متغيرات صحيحة موجبة)، عدلها العديد من المؤلفين من بعده لتتناسب مع أغراضهم المختلفة، قد تشير «دالة أكرمان» إلى أي من الاشكال المختلفة للدالة الاصلية. واحدة من هاته الدوال وهي نسخة مشتركة فيما بينهم. وهي دالة أكرمان - بيتر ذات المتغيرين, وهي معرفة كما يلي: (ar) 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, the two-argument Ackermann–Péter function is defined as follows for nonnegative integers m and n: (en) In matematica, la funzione di Ackermann è una funzione che ha come dominio l'insieme delle terne di numeri naturali e come codominio i numeri naturali. Essa è definita per ricorrenza nel seguente modo: Un caso particolare è la funzione di Ackermann a due argomenti , così definita: La funzione di Ackermann è un esempio di funzione ricorsiva che non è primitiva ricorsiva poiché cresce più velocemente di qualsiasi funzione ricorsiva primitiva. Risulta quindi una funzione con una complessità estremamente elevata anche per valori di input semplici. (it) In de berekenbaarheidstheorie is de ackermannfunctie, genoemd naar Wilhelm Ackermann, die de functie in 1926 opstelde, een van de eenvoudigste en vroegst ontdekte voorbeelden van een totale berekenbare functie die niet primitief recursief is. Alle primitieve recursieve functies zijn totaal en berekenbaar, maar de ackermannfunctie illustreert dat niet alle totale berekenbare functies primitief recursief zijn. De ackermannfunctie is een extreem snel toenemende functie met behulp waarvan de grenzen aan computer- en rekenmodellen in de theoretische informatica kunnen worden aangetoond. Na Ackermanns publicatie van de functie (die drie natuurlijke getallen als argumenten had), hebben veel auteurs het concept aangepast voor verschillende doeleinden, zodat tegenwoordig "ackermannfunctie" kan verw (nl) Funkcja Ackermanna – funkcja matematyczna odkryta przez Wilhelma Ackermanna w 1928 roku. Cechą charakterystyczną tej dwuargumentowej funkcji jest jej nadzwyczaj szybki wzrost. Funkcja Ackermanna jest prostym przykładem funkcji rekurencyjnej, niebędącej funkcją pierwotnie rekurencyjną. Funkcje pierwotnie rekurencyjne to większość znanych funkcji, między innymi dodawanie, funkcja wykładnicza itp. Inną funkcją o własnościach podobnych do funkcji Ackermanna (tzn. będąca rekurencyjną i nie pierwotnie rekurencyjną) jest funkcja Sudana. (pl) Na teoria da computabilidade, a Função de Ackermann, nomeada por Wilhelm Ackermann, é um dos mais simples e recém-descobertos exemplos de uma função computável que não são funções recursivas primitivas. Todas as funções recursivas primitivas são totais e computáveis, mas a Função de Ackermann mostra que nem toda função total-computável é recursiva primitiva. Como se pode ver, seu valor cresce rapidamente, até mesmo para pequenas entradas. Por exemplo, A(4,2) resulta em um inteiro com 19.729 dígitos. (pt) Ackermannfunktionen är ett exempel på en beräkningsbar funktion som inte är primitivt rekursiv. Ackermannfunktionen definieras för icke-negativa heltal och enligt: Från definitionen syns tydligt att för växer väldigt snabbt, redan för låga värden på n. Exempelvis är skrivet i decimal form ett heltal med över 19 000 siffror. För specifika värden på , då kan beskrivas med relativt enkla medel: För större värden på växer funktionen alltför snabbt för att beskrivas med några av de elementära räknesätten. I stället kan Knuths pilnotation användas. Generellt gäller att Och då (sv)
rdfs:label Ackermann function (en) دالة أكرمان (ar) Funció d'Ackermann (ca) Ackermannova funkce (cs) Ackermannfunktion (de) Akermana funkcio (eo) Función de Ackermann (es) Funzione di Ackermann (it) Fonction d'Ackermann (fr) 아커만 함수 (ko) アッカーマン関数 (ja) Ackermannfunctie (nl) Funkcja Ackermanna (pl) Функция Аккермана (ru) Função de Ackermann (pt) Ackermannfunktionen (sv) 阿克曼函數 (zh) Функція Акермана (uk)
owl:sameAs freebase:Ackermann function yago-res:Ackermann function wikidata:Ackermann function dbpedia-ar:Ackermann function dbpedia-ca:Ackermann function dbpedia-cs:Ackermann function dbpedia-de:Ackermann function dbpedia-eo:Ackermann function dbpedia-es:Ackermann function dbpedia-fa:Ackermann function dbpedia-fi:Ackermann function dbpedia-fr:Ackermann function dbpedia-he:Ackermann function dbpedia-hu:Ackermann function dbpedia-it:Ackermann function dbpedia-ja:Ackermann function dbpedia-ko:Ackermann function dbpedia-lmo:Ackermann function dbpedia-nl:Ackermann function dbpedia-pl:Ackermann function dbpedia-pms:Ackermann function dbpedia-pt:Ackermann function dbpedia-ru:Ackermann function dbpedia-sr:Ackermann function dbpedia-sv:Ackermann function dbpedia-tr:Ackermann function dbpedia-uk:Ackermann function dbpedia-vi:Ackermann function dbpedia-zh:Ackermann function https://global.dbpedia.org/id/39XdW
prov:wasDerivedFrom wikipedia-en:Ackermann_function?oldid=1123526697&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Ackermann_function
is dbo:wikiPageDisambiguates of dbr:Ackermann
is dbo:wikiPageRedirects of dbr:Ackerman's_function dbr:Ackerman_function dbr:Akerman_function dbr:Akermann_function dbr:Ackermann_Function dbr:Ackermann_numbers dbr:Inverse_Ackerman's_function dbr:Inverse_Ackermann_function dbr:Inverse_Ackermann dbr:Ackermann's_function dbr:Ackermann-Peter_function dbr:Ackermann_Number dbr:Ackermann_algorithm dbr:Ackermann_number dbr:Péter_function
is dbo:wikiPageWikiLink of dbr:Primitive_recursive_function dbr:Robert_Tarjan dbr:Rosetta_Code dbr:List_of_dynamical_systems_and_differential_equations_topics dbr:Paris–Harrington_theorem dbr:Path_ordering_(term_rewriting) dbr:Decider_(Turing_machine) dbr:Hyperoperation dbr:Reuben_Goodstein dbr:Unit_distance_graph dbr:Double_exponential_function dbr:Double_recursion dbr:Dynamic_connectivity dbr:Initial_algebra dbr:List_of_mathematical_functions dbr:List_of_mathematical_logic_topics dbr:Pentation dbr:Combinatorial_explosion dbr:Computability_theory dbr:Computable_function dbr:Ordinal_collapsing_function dbr:Tree_spanner dbr:General_recursive_function dbr:Constructive_set_theory dbr:Conway_chained_arrow_notation dbr:Range_query_(data_structures) dbr:Alpha_(disambiguation) dbr:Component_(graph_theory) dbr:Hales–Jewett_theorem dbr:Kruskal's_algorithm dbr:Kruskal's_tree_theorem dbr:PR_(complexity) dbr:Planar_separator_theorem dbr:Sudan_function dbr:Davenport–Schinzel_Sequences_and_Their_Geometric_Applications dbr:Davenport–Schinzel_sequence dbr:Wilhelm_Ackermann dbr:Gabriel_Sudan dbr:Laver_table dbr:Ackerman's_function dbr:Ackerman_function dbr:Akerman_function dbr:Akermann_function dbr:Algorithm_characterizations dbr:Exponentiation dbr:Ackermann dbr:Ackermann_Function dbr:Ackermann_numbers dbr:PL/SQL dbr:Fast-growing_hierarchy dbr:Goodstein's_theorem dbr:Graham's_number dbr:Iterated_logarithm dbr:Kinetic_priority_queue dbr:Knuth's_up-arrow_notation dbr:List_of_Romanian_inventors_and_discoverers dbr:Ramsey_theory dbr:Recursion dbr:Asymptotically_optimal_algorithm dbr:Inverse_Ackerman's_function dbr:Inverse_Ackermann_function dbr:Tetration dbr:Arrangement_of_lines dbr:Ackermann's_formula dbr:LFE_(programming_language) dbr:LOOP_(programming_language) dbr:Large_numbers dbr:BlooP_and_FlooP dbr:Ehrenfeucht–Mycielski_sequence dbr:Register_machine dbr:Disjoint-set_data_structure dbr:Borůvka's_algorithm dbr:Minimum_spanning_tree dbr:Orders_of_magnitude_(numbers) dbr:Recursion_(computer_science) dbr:Rózsa_Péter dbr:Vector_addition_system dbr:Exponential_growth dbr:F-algebra dbr:List_of_types_of_functions dbr:Nonelementary_problem dbr:Superfunction dbr:Parallel_algorithms_for_minimum_spanning_trees dbr:Steinhaus–Moser_notation dbr:Inverse_Ackermann dbr:Ackermann's_function dbr:Ackermann-Peter_function dbr:Ackermann_Number dbr:Ackermann_algorithm dbr:Ackermann_number dbr:Péter_function
is foaf:primaryTopic of wikipedia-en:Ackermann_function