Ackermannfunktionen

Ackermannfunktionen är ett exempel på en beräkningsbar funktion som inte är primitivt rekursiv.

Ackermannfunktionen definieras för icke-negativa heltal $m$ och $n$ enligt: $A(m,n)={\begin{cases}n+1&\ m=0\\A(m-1,1)&\ m>0,n=0\\A(m-1,A(m,n-1))&\ m>0,n>0.\end{cases}}$

Från definitionen syns tydligt att för $m>3$ växer $A(m,n)$ väldigt snabbt, redan för låga värden på n. Exempelvis är $A(4,2)$ skrivet i decimal form ett heltal med över 19 000 siffror.

För specifika värden på $n$ , då $m<4$ kan $A(m,n)$ beskrivas med relativt enkla medel:

A(m,n)={\begin{cases}n+1&\ m=0\\n+2&\ m=1\\2n+3&\ m=2\\2^{n+3}-3&\ m=3\\\end{cases}}

För större värden på $m$ 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

A(m,n)=2\uparrow ^{m-2}(n+3)-3.

Med hjälp av denna beskrivning kan rekursionen av $A(4,2)$ göras något enklare.

A(4,2)=2\uparrow ^{4-2}(2+3)-3=2\uparrow ^{2}(5)-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2-3=2^{2^{2^{2^{2}}}}-3=2^{65536}-3

Och då

\log(2^{65536})=65536\cdot \log(2)\approx 19728{,}3

förstås att detta tal utskrivet i decimal form har 19 729 siffror.

Ackermannstal

Värden på $A(m,n)$
		0	1	2	3	4	$n$
		$n$
$m$	0	1	2	3	4	5	$n+1$
	1	2	3	4	5	6	$n+2=2+(n+3)-3$
	2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
	3	5	13	29	61	125	$2^{(n+3)}-3$
	4	13 = ${2^{2^{2}}}-3$	65533 = ${2^{2^{2^{2}}}}-3$	2⁶⁵⁵³⁶ − 3 = ${2^{2^{2^{2^{2}}}}}-3$	${2^{2^{65536}}}-3$ = ${2^{2^{2^{2^{2^{2}}}}}}-3$	${2^{2^{2^{65536}}}}-3$ = ${2^{2^{2^{2^{2^{2^{2}}}}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n+3\end{matrix}}$
	5	65533 = $2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
	6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$

Se även

Wilhelm Ackermann

v • r

Mycket stora tal

I storleksordning

Tusen · Tiotusen · Hundratusen · Miljon · Tio miljoner · Hundra miljoner · Miljard · Biljon · Biljard · Triljon · Triljard · Kvadriljon · Kvadriljard · Kvintiljon · Kvintiljard · Sextiljon · Sextiljard · Septiljon · Septiljard · Oktiljon · Oktiljard · Noniljon · Noniljard · Deciljon · Deciljard · Undeciljon · Undeciljard · Duodeciljon · Duodeciljard · Tredeciljon · Tredeciljard · Quattuordeciljon · Quattuordeciljard · Quindeciljon · Quindeciljard · Sexdeciljon · Sexdeciljard · Googol · Googolplex · Skewes tal · Mosers tal · Grahams tal · TREE(3) · SSCG(3) · Rayos tal · Transfinita tal

Uttrycksmetoder

Notationer	Grundpotensform · Knuths pilnotation · Conways kedjepilnotation · Steinhaus–Mosers notation

Operatorer	Hyperoperator (Tetraering · Pentaering) · Ackermannfunktionen · Grzegorczyks hierarki · Snabbväxande hierarki

Relaterade artiklar

Utökade reella tallinjen · Gigantiska primtal · Indefinita och fiktiva tal · Infinitesimal · Stora primtal · Lista över tal · Långa och korta skalan för stora tal · Tal · Räkneord · Storleksordningar · Tvåpotens · Trepotens · Tiopotens · Saganenhet · Titaniska primtal

Namn · Histora

Read other articles:

Focke-Wulf Ta 152

Ta 152 Ta 152 H-1 yang dirampas Inggris, Werknummer 150168, dibongkar tahun 1946. Jenis Pencegat Pembuat Focke-Wulf Perancang Kurt Tank Penerbangan perdana akhir 1944 Diperkenalkan Januari 1945 (service entry) Dipensiunkan Mei 1945 Pengguna utama Luftwaffe Jumlah Tidak diketahui[1] Dikembangkan dari Focke-Wulf Fw 190 Focke-Wulf TA-152 adalah pesawat tempur pencegat yang dirancang oleh Kurt Tank dan diproduksi Focke-Wulf. Pesawat ini memiliki ketinggian terbang tertinggi dari sem...

Stace

StacePortrait de Stace (publié entre 1523 et 1593)BiographieNaissance 45NaplesDécès 96Naples (?)Nom dans la langue maternelle StatiusÉpoque Empire romainActivités Poète, écrivainPère Publius Papinius Statius (d)Gens Statii (en), Papinii (en)Autres informationsGenre artistique Littérature épique (en)Œuvres principales Silves (d), Thébaïdemodifier - modifier le code - modifier Wikidata Stace (Publius Papinius Statius) est un poète de langue latine de la Rome antique, né à Naples...

Seruling

Berbagai macam seruling. Orang Nubian Mesir sedang bermain seruling Seruling atau suling adalah alat musik dari keluarga alat musik tiup kayu atau terbuat dari bambu. Suara seruling berciri lembut dan dapat dipadukan dengan alat musik lainnya dengan baik.[1] Seruling modern untuk para ahli umumnya terbuat dari perak, emas, atau campuran keduanya, sedangkan seruling untuk pelajar umumnya terbuat dari nikel-perak, atau logam yang dilapisi perak. Seruling konser standar ditalakan di C da...

Jurica Vranješ

Jurica Vranješ Jurica Vranješ menjelang laga versus Bayern MunichInformasi pribadiTanggal lahir 31 Januari 1980 (umur 44)Tempat lahir Osijek, YugoslaviaTinggi 1,86 m (6 ft 1 in)[1]Posisi bermain GelandangKarier junior0000–1997 NK OsijekKarier senior*Tahun Tim Tampil (Gol)1997–2000 NK Osijek 54 (10)2000–2003 Bayer Leverkusen 46 (0)2003–2005 VfB Stuttgart 39 (0)2005–2010 Werder Bremen 90 (5)2010–2011 → Gençlerbirliği (pinjam) 13 (0)2011–2012 Aris...

Man Hunt (1985 film)

1985 film This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Man Hunt 1985 film – news · newspapers · books · scholar · JSTOR (April 2019) (Learn how and when to remove this template message) Man HuntDVD coverDirected byFabrizio De AngelisWritten byFabrizio De AngelisDardano Sacchetti (story)Produced byFab...

Fibre d'alpaga

Pour les articles homonymes, voir Alpaga (homonymie). Laine d'alpaga. La fibre d'alpaga est la fibre textile donnée par l'alpaga Vicugna pacos. Le terme désigne indifféremment la laine et le tissu produit avec les poils de cet animal. La laine d'alpaga est une fibre de très haut de gamme, plus douce, plus chaude, plus résistante et plus légère que la laine de mouton. On peut tondre l'animal tous les ans, mais sa toison peut être gardée deux, voire trois ans. Les poils mesurent de 15...

Liste des sénateurs des États-Unis pour le Mississippi

Depuis son adhésion à l'Union, le 10 décembre 1817, l'État du Mississippi élit deux sénateurs, membres du Sénat fédéral. Liste Liste des sénateurs des États-Unis représentant le Mississippi Sénateur de classe 1 Congrès Sénateur de classe 3 1er(1789-1791) 2e(1791-1793) 3e(1793-1795) 4e(1795-1797) 5e(1797-1799) 6e(1799-1801) 7e(1801-1803) 8e(1803-1805) 9e(1805-1807) 10e(1807-1809) 11e(1809-1811) 12e(1811-1813) 13e(1813-1815) 14e(1815-1817) 15e(1817-1819) 16e(1819-1821) 17e(1821-1...

Stratford-on-Avon District

Non-metropolitan district in Warwickshire, England This article is about the local government district. For the town, see Stratford-upon-Avon. For other uses of the name, see Stratford (disambiguation). Non-metropolitan district in EnglandStratford-on-Avon DistrictNon-metropolitan districtRiver Avon at Stratford-upon-AvonShown within WarwickshireSovereign stateUnited KingdomConstituent countryEnglandRegionWest MidlandsAdministrative countyWarwickshireAdmin. HQStratford-upon-AvonGovernmen...

Charles Maurras

French author, politician, poet, and critic (1868–1952) Charles MaurrasMaurras in 1937BornCharles-Marie-Photius Maurras(1868-04-20)20 April 1868Martigues, Bouches-du-Rhône, FranceDied16 November 1952(1952-11-16) (aged 84)Tours, FranceEra20th century philosophyRegionWestern philosophySchoolMaurrassismePositivismRoyalismIntegral nationalismReactionismInstitutionsAction FrançaiseNotable ideasMaurrassisme This article is part of a series onConservatism in France Ideologies French nationa...

Operation Okra

Australian contribution to the military intervention against ISIL Operation OkraPart of the American-led intervention in Iraq, Foreign involvement in the Syrian Civil War and the War against the Islamic StateAn Australian F/A-18A Hornet over Iraq in 2017LocationIraq and SyriaObjectiveAustralia's contribution to the War against ISILDate31 August 2014 – present[1]Executed byAustralian Army Royal Australian Air ForceAustralian Signals Directorate[2] vteWar in Iraq (2013–...

Bernard Lonergan

Canadian philosopher and theologian (1904–1984) Lonergan redirects here. For the surname, see Lonergan (surname). The ReverendBernard LonerganSJ CCLonergan at Boston CollegeBornBernard Joseph Francis Lonergan(1904-12-17)17 December 1904Buckingham, Quebec, CanadaDied26 November 1984(1984-11-26) (aged 79)Pickering, Ontario, Canada Part of a series onCatholic philosophy Aquinas, Scotus, and Ockham Ethics Cardinal virtues Just price Just war Principle of Double Effect Probabilis...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。概要壱万円日本銀行券（「壱」が大字）弐千円日本銀行券（「弐」が大字）漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Aquayamycin

Aquayamycin[1] Names Preferred IUPAC name (3R,4aR,12bS)-9-[(2R,4R,5S,6R)-4,5-Dihydroxy-6-methyloxan-2-yl]-3,4a,8,12b-tetrahydroxy-3-methyl-3,4,4a,12b-tetrahydrotetraphene-1,7,12(2H)-trione Identifiers CAS Number 26055-63-0 Y 3D model (JSmol) Interactive image ChemSpider 66147 Y MeSH aquayamycin PubChem CID 73441 CompTox Dashboard (EPA) DTXSID40948932 InChI InChI=1S/C25H26O10/c1-10-19(28)14(26)7-15(35-10)11-3-4-12-17(20(11)29)21(30)13-5-6-24(33)9-23(2,32)8-16(27)25(24,34)18(...

SMP Muhammadiyah Batam

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. SMP Muhammadiyah BatamInformasiJenisSekolah SwastaAlamatLokasi, Batam, Kepri, IndonesiaMoto SMP Muhammadiyah Batam, merupakan salah satu Sekolah Menengah Pertama swasta yang ada di Batam, Provinsi Kepulauan Riau. Sama dengan SMP pada umumnya di ...

Flag of the United States Air Force

United States Air ForceOther namesCeremonial Departmental Flag, United States Air Force Departmental Flag, HQ USAF flagUseOther Proportion33:26Adopted26 March 1951DesignThe U.S. Air Force's crest surrounded by thirteen white five-pointed stars on a blue field.Designed byDorothy G. Gatchell UseOther Proportion4:3AdoptedMarch 1951DesignThe U.S. Air Force's crest surrounded by thirteen white five-pointed stars on a blue field.Designed byDorothy G. Gatchell The flag of the United State...

منتخب البرازيل لهوكي الحقل للسيدات

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أبريل 2024) منتخب البرازيل لهوكي الحقل للسيدات البلد البرازيل التصنيف بوابة البرازيل ب...

Khmelnytskyi

Sudut kota Khmelnytskyi Khmelnytskyi (Ukraina: Хмельницький) merupakan sebuah kota di Ukraina. Kota ini letaknya di bagian tengah. Tepatnya di Oblast Khmelnytskyi. Pada tahun 2005, kota ini memiliki jumlah penduduk sebesar 254.000 jiwa dan memiliki luas wilayah 90 km². Kota ini memiliki angka kepadatan penduduk sebesar 2.822 jiwa/km². Pranala luar Lihat entri Khmelnytskyi di kamus bebas Wiktionary. khmelnytsky.com Diarsipkan 2018-03-29 di Wayback Machine. - Khmelnytskyi Cit...

Ron Wilson (ice hockey, born 1955)

Canadian- American ice hockey coach For the other Ron Wilson associated with ice hockey, see Ron Wilson (ice hockey, born 1956). Ice hockey player Ron Wilson Wilson in 2010Born (1955-05-28) May 28, 1955 (age 69)Windsor, Ontario, CanadaHeight 5 ft 11 in (180 cm)Weight 175 lb (79 kg; 12 st 7 lb)Position DefenceShot RightPlayed for Toronto Maple LeafsMinnesota North StarsCoached for Mighty Ducks of AnaheimWashington CapitalsSan Jose SharksToronto Maple Lea...

Bureau international des Expositions

Bureau International des Expositions(FR) Bureau international des Expositions(EN) Bureau International of Exposition AbbreviazioneBIE TipoIntergovernativa Fondazione22 novembre 1928 Scopoculturale, politico Sede centrale Parigi Segretario Generale Choi Jai-chul Lingua ufficialefrancese, inglese Membri170 membri (171 membri dal 2030) Sito web e Sito web Modifica dati su Wikidata · Manuale Il Bureau International des Expositions (abbreviato in BIE) è l'organizzazione intergovernativa che...

كأس جمهورية أيرلندا 2012

كأس جمهورية أيرلندا 2012 تفاصيل الموسم كأس جمهورية أيرلندا النسخة 89 البلد جمهورية أيرلندا التاريخ بداية:30 مارس 2012 نهاية:4 نوفمبر 2012 المنظم اتحاد أيرلندا لكرة القدم البطل ديري سيتي مباريات ملعوبة 42 عدد المشاركين 40 كأس جمهورية أيرلندا 2011 كأس �...