康威鏈式箭號表示法

康威鏈式箭號表示法是由約翰·何頓·康威發明的,用來表示大數[1]。形式上看起來會像這樣:2→3→4→5→6。

定義

康威鏈式箭號表示法的長度定義如下:

  • 任何一個正整數是長度為1的康威鏈。
  • 假若有一個長度是n的康威鏈,後面加上→和一個正整數,此時形成的鏈長度為n+1。

如果兩個康威鏈代表相同的整數,那麼就說它們是等價的。 下面四個規則說明如何用康威鏈表示整數,其中是正整數,是一個較短的康威鏈:

  1. 康威鏈表示正整數
  2. 代表指數
  3. 等價於
  4. 等價於
    (在這裡,出現次,出現次,括號數量為)。

第四條規則可以以遞迴關係式列出,避免省略號的出現:

4a.
4b.

上面的四條規則可用來定義所有的康威鏈。例如長度為3的康威鏈,利用第四條規則,基本上長度仍然一樣,但會是遞減的,當遞減到1時,就可以利用第三條規則來使長度縮短,使得它可利用第二條規則來計算出來。

性質

  1. 長度為3的康威鏈對應hyper運算符高德納箭號表示法
  2. X→Y形式上如同X→p(設Y是一個較短的康威鏈,如同X一樣),因此:
  3. 一個康威鏈的開頭是冪。
  4. 1→Y等價於1。
  5. X→1→Y等價於X。
  6. 2→2→Y等價於4。
  7. X→2→2等價於X→(X),其中後面的X是先被算出來的整數,如a→b→2→2 = a→b→(a→b) = a→b→ab

康威鏈不能被拆分,其箭號並不是二元運算符。其他二元運算符具有交換律結合律,如2 + 3 = 3 + 2,2 + 3 + 2 = (2 + 3) + 2 = 2 + (3 + 2),或者是按照規定的順序,如234這類指數是從右至左計算,先計算34 = 81,再計算281。康威鏈並不符合上述性質。例如:

第一個式子並不等於下面任何式子。

例子

例子很快會變得非常複雜,先從簡單的開始(其中有些例子也會應用高德納箭號表示法):

n

= n (規則1)

p→q

= pq (規則2)
例如 3→4 = 34 = 81

1→(任何康威鏈)

= 1,因為任何康威鏈最終可以被簡化成一個數字,而1的任何次方都是1。 (事實上,任何含有1的康威鏈,在1後面的那些數字和箭號都可直接消去,一個例子如X→1→Y = X。)

4→3→2

= 4→(4→(4)→1)→1(規則4),從內向外展開。
= 4→(4→4→1)→1(去掉多餘的括號)
= 4→(4→4)→1(規則3)
= 4→(44)→1(規則2)
= 4→(256)→1(計算指數)
= 4→256→1(去括號)
= 4→256(規則3)
= 4256(規則2)

利用高德納箭號表示法可以很容易解決:

2→2→4

= 2→(2)→3(規則4)
= 2→2→3(去括號)
= 2→2→2(規則4,去括號)
= 2→2→1(規則4,去括號)
= 2→2(規則3)
= 4(規則2)(事實上,任何以2→2為開頭的康威鏈其值均為4,本例是一個例子,應用性質6)

高德納箭號表示法:

2→4→3

= 2→(2→(2→(2)→2)→2)→2(規則4)
= 2→(2→(2→2→2)→2)→2(去括號)
= 2→(2→(4)→2)→2(性質6)
= 2→(2→4→2)→2(去括號)
= 2→(2→(2→(2→(2)→1)→1)→1)→2(規則4)
= 2→(2→(2→(2→2→1)→1)→1)→2(去括號)
= 2→(2→(2→(2→2)))→2(規則3)
= 2→(2→(2→(4)))→2(規則2)
= 2→(2→(16))→2(規則2)
= 2→65536→2(規則2)
= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1(規則4),其中括號出現65535次
= 2→(2→(2→(...2→(2→(2))...)))(規則3)
= 2→(2→(2→(...2→(4)...)))(規則2)
= 2→(2→(2→(...16...)))(規則2)
= (其中2出現216 = 65536次) = 655362(見迭代冪次

若用高德納箭號表示法可得

2→3→2→2

= 2→3→(2→3)→1(規則4)
= 2→3→8(規則2和規則3)(利用高德納箭號表示法即為
= 2→(2→2→7)→7(規則4)
= 2→4→7(性質6,利用高德納箭號表示法即為
= 2→(2→(2→2→6)→6)→6(規則4)
= 2→(2→4→6)→6(性質6)
= 2→(2→(2→(2→2→5)→5)→5)→6(規則4)
= 2→(2→(2→4→5)→5)→6(性質6)
= 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6(規則4)
= 2→(2→(2→(2→4→4)→4)→5)→6(性質6)
= 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4)→5)→6(規則4)
= 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6(性質6)
= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6(利用前面的例子)
= 大到無法想像的數

高德納箭號表示法:

3→2→2→2

= 3→2→(3→2)→1(規則4)
= 3→2→9(規則2和規則3)
= 3→3→8(規則4)

高德納箭號表示法:

3→2→3→3

= 3→2→(3→2→(3→2)→2)→2(規則4)
= 3→2→(3→2→9→2)→2(規則2)
= 3→2→(3→2→(3→2→(...3→2→(3→2)→1...)→1)→1)→2(規則4),其中3→2出現10次,也就是原本的1個,加上括號裡的9個。
= 3→2→(3→2→(3→2→(...3→2→(3→2)...)))→2(規則3),3→2出現10次。
= 3→2→(3→2→(3→2→(...3→2→9...)))→2(規則2),3→2出現9次。
= 3→2→(3→2→(3→2→(...3→3→8...)))→2(規則4),3→2出現8次。
= 3→2→(3→2→(3→2→(......)))→2(高德納箭號表示法),3→2出現8次。
= 3→2→(3→2→(3→2→(...3→2→()...)))→2
= 3→2→(3→2→(3→2→(......)))→2(高德納箭號表示法),3→2出現7次。
= ...
= 3→2→→2(高德納箭號表示法)
= 3→2→(3→2→(...3→2→(3→2)→1...)→1)→1(規則4),其中3→2出現次。
= 3→2→(3→2→(...3→2→(3→2)))(規則3),其中3→2出現次。
= ,其中向上箭號出現次。
=

可見得3→2→3→3為使用高德納箭號表示法都難以表示的數,這個例子可證明,使用康威鏈式箭號表示法表示大數的效率會比高德納箭號表示法高很多(葛立恆數則是另一個例子)。

一般性的例子

簡單的例子:

最後利用了性質1。

最後利用了
最後利用了

對於任何康威鏈X,設,則(見複合函數)。

,則,所以

例如

進而:

我們可以進一步一般化。假設,則,就是說

根據上面可知, 以及,所以

阿克曼函數

阿克曼函數可以使用康威鏈式箭號表示法來表示:

A(m, n) = (2 → (n + 3) → (m − 2)) − 3 for m > 2

相反的

2 → nm = A(m + 2,n − 3) + 3 for n > 2

(n=1和n=2有特別的規定,A(m, -2) = -1 以及 A(m, -1) = 1。)

葛立恆數

葛立恆數 無法用康威鏈式箭號表示法來簡單的表示,但是可以訂出簡潔的上下界。設 ,則 (見複合函數),可以得到

證明:這裡會使用到規則3和規則4:

(這裡有64個

(這裡有64個

(這裡有64個
(這裡有65個

由於嚴格遞增函數

這給出了上下界。

利用康威鏈式箭號表示法,很容易表示遠遠大於葛立恆數的數:

其中遠遠大於,因此遠遠大於葛立恆數。

參見

參考資料

  1. ^ 約翰·何頓·康威. On Numbers and Games(論數字與博弈). A K PETERS Limited. 2001. ISBN 1568811276. 

外部連結

Read other articles:

Badan Penelitian dan Pengembangan Industri Kementerian Perindustrian Republik IndonesiaGambaran umumDasar hukumPeraturan Presiden Nomor 29 Tahun 2015Susunan organisasiKepala Badan-Situs webhttp://www.kemenperin.go.id/ Badan Penelitian dan Pengembangan Industri merupakan unsur pendukung pada Kementerian Perindustrian Republik Indonesia yang berada di bawah dan bertanggung jawab kepada Menteri Perindustrian Republik Indonesia.[1] Pranala luar (Indonesia) Situs web resmi Kementerian...

 

Maghribi beralih ke halaman ini. Untuk salah satu dari salat lima waktu, lihat Salat Maghrib. Kerajaan Marokoالمملكة المغربية Al-Mamlakah al-Magribiyah (Arab) ⵜⴰⴳⵍⴷⵉⵜ ⵏ ⵍⵎⵖⵔⵉⴱ Tageldit n Lmaɣrib (Berber) Royaume du Maroc (Prancis) Bendera Lambang Semboyan: الله، الوطن، الملك Allāh, al-Waṭan, al-Malik (Arab: Allah, Negara, Raja)Lagu kebangsaan:   ⵉⵣⵍⵉ ⴰⵏⴰⵎⵓⵔ ⵏ ⵍⵎⵖⵔⵉⴱ  النشي...

 

Henry III dari InggrisPatung makam Raja Henry III di Westminster Abbey, skt. 1272Raja Inggris (selengkapnya...) Berkuasa19 Oktober 1216 – 16 November 1272Penobatan28 Oktober 1216, Gloucester17 Mei 1220, Westminster AbbeyPendahuluJohnPenerusEdward IRegents Lihat William Marshal (1216–1219)Hubert de Burgh (1219–1227) Informasi pribadiKelahiran(1207-10-01)1 Oktober 1207Kastil Winchester, HampshireKematian16 November 1272(1272-11-16) (umur 65)Westminster, LondonPemakamanWestm...

Houston StreetEastward view of Houston Street in Downtown San AntonioFormer name(s)Rivas Street, El Paseo Del RioLocationSan AntonioPostal code78205 and 78207 (Downtown)West end I-35 (Downtown) NW 26th Street (Terminus)East end I-37 (Downtown) FM 1346 (Terminus) Houston Street is one of San Antonio's oldest and most popular streets. Situated in the middle of the city's central business district, it is a major pedestrian thoroughfare and commercial district. Retail shops, chic restau...

 

2018–2022 concert tour by Iron Maiden Legacy of the Beast World TourWorld tour by Iron MaidenOfficial tour posterLocationEuropeNorth AmericaLatin AmericaAsiaOceaniaStart date26 May 2018End date27 October 2022No. of shows140Iron Maiden concert chronology The Book of Souls World Tour(2016–2017) Legacy of the Beast World Tour(2018–2022) The Future Past World Tour(2023–2024) The Legacy of the Beast World Tour was a concert tour by English heavy metal band Iron Maiden, named after the comi...

 

Satelit ECHO dikenal juga sebagai satelit HIRO. HIRO ialah satelit komunikasi pasif pertama Amerika Serikat. Terbuat dari balon metal, berdiameter 30 meter (HIRO 1) dan 42 meter (HIRO 2). Berturut-turut, kedua satelit itu diluncurkan pada tahun 1960 dan 1964 oleh NASA. Echo 1 digelembungkan penuh di hanggar US Navy di Weeksville, North Carolina. Hiro 1 merupakan satelit komunikasi pasif: berfungsi sebagai pemantul, bukan pemancar. Setelah ditempatkan di orbit bumi rendah, sinyal akan dikirim ...

Lucio Battistialbum in studioArtistaLucio Battisti Pubblicazione5 marzo 1969 Durata38:59 Dischi1 Tracce12 GenerePop EtichettaDischi Ricordi (SMRL 6063) ProduttoreLucio Battisti e Mogol ArrangiamentiLucio Battisti, Gian Piero Reverberi, Detto Mariano Velocità di rotazione33 giri Formatidisco in vinile di 30 cm Altri formatiaudiocassetta, Stereo8 Certificazioni FIMI (dal 2009)Dischi d'oro Italia[1](vendite: 25 000+) Lucio Battisti - cronologiaAlbum precedente—Album suc...

 

أكتروسمعلومات عامةالنوع truck model (en) موقع الويب mercedes-benz-trucks.com المنظومة الاقتصاديةالعلامة التجارية مرسيدس-بنز تعديل - تعديل مصدري - تعديل ويكي بيانات أكتروس (بالألمانية: Actros) هي شاحنة نقل ثقيلة من صنع شركة مرسيدس بنز الألمانية. تستخدم هذه الشاحنة لنقل البضائع والسلع وتاتي بمحر...

 

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند  الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمار...

American manufacturing company Spectrum Brands Holdings, Inc.Company typePublicTraded asNYSE: SPBRussell 1000 ComponentIndustryManufacturingPredecessorRayovac CorporationFoundedJanuary 17, 1906; 118 years ago (1906-01-17) (as French Battery Company)Madison, Wisconsin, U.S.HeadquartersMiddleton, Wisconsin, U.S.Key peopleDavid M. Maura (executive chairman & CEO)ProductsBlack & Decker appliancesGeorge Foreman grillsRemington productsMarineland aquariumsTetra fish c...

 

Polygon with 13 edges Regular tridecagonA regular tridecagonTypeRegular polygonEdges and vertices13Schläfli symbol{13}Coxeter–Dynkin diagramsSymmetry groupDihedral (D13), order 2×13Internal angle (degrees)≈152.308°PropertiesConvex, cyclic, equilateral, isogonal, isotoxalDual polygonSelf In geometry, a tridecagon or triskaidecagon or 13-gon is a thirteen-sided polygon. Regular tridecagon A regular tridecagon is represented by Schläfli symbol {13}. The measure of each internal angle of ...

 

County in Virginia, United States For other uses, see Orange County (disambiguation). This article needs to be updated. Please help update this article to reflect recent events or newly available information. (October 2019) County in VirginiaOrange CountyCountyOrange County Courthouse SealLocation within the U.S. state of VirginiaVirginia's location within the U.S.Coordinates: 38°14′N 78°01′W / 38.24°N 78.01°W / 38.24; -78.01Country United StatesState ...

Malus Malus ‘Purple Prince’[1]DataSumber dariapel dan apple wood TumbuhanJenis buahpome TaksonomiDivisiTracheophytaSubdivisiSpermatophytesKladAngiospermaeKladmesangiospermsKladeudicotsKladcore eudicotsKladSuperrosidaeKladrosidsKladfabidsOrdoRosalesFamiliRosaceaeSubfamiliMaloideaeGenusMalus Mill., 1754 Tipe taksonomiMalus sylvestris SpesiesLihat tekslbs Malus (/ˈmeɪləs/[2] or /ˈmæləs/) adalah sebuah genus dari sekitar 30–55 spesies[3] pohon tumbuha...

 

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: El Djem – news · newspapers · books · scholar · JSTOR (November 2021) (Learn how and when to remove this message) Place in Mahdia Governorate, TunisiaEl Djem الجمّThysdrusEl DjemThe skyline of El DjemEl DjemLocation in TunisiaCoordinates: 35°17′48″N 1...

 

Vengeful Japanese ghosts This article is about the mythological Japanese spirit. For the Korean dynasty, see Goryeo.You can help expand this article with text translated from the corresponding article in Japanese. Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machin...

Méchy Administration Pays France Région Grand Est Département Moselle Arrondissement Metz Commune Sanry-lès-Vigy Statut Ancienne commune Code postal 57640 Démographie Population 97 hab. (1900) Géographie Coordonnées 49° 11′ 19″ nord, 6° 15′ 52″ est Historique Fusion 1811 Localisation Géolocalisation sur la carte : France Méchy Géolocalisation sur la carte : France Méchy Géolocalisation sur la carte : Moselle Méchy Géol...

 

Theban tomb Theban tomb TT407Burial site of BintenduanetjerTT 407 is located within the tomb of Kheruef TT192LocationEl-Assasif, Theban Necropolis← PreviousTT406Next →TT408 [1] Bintenduanetjerin hieroglyphs Era: New Kingdom(1550–1069 BC) Tomb TT407, located in the necropolis of El-Assasif in Thebes, Egypt, is the tomb of Bintenduanetjer, who was the Chamberlain of the Divine Adoratrice, and dates to the Saite period. The tomb is located off the south side of ...

 

River in Iowa, United StatesMaquoketa RiverThe North Fork of the Maquoketa River at Dyersville, Iowa in 1996Maquoketa River highlightedEtymologyMaquaw-Autaw, Bear River in MeskwakiLocationCountryUnited StatesStateIowaPhysical characteristicsSource  • coordinates42°43′08″N 91°42′39″W / 42.7189°N 91.7107°W / 42.7189; -91.7107 MouthMississippi River • elevation591 ft (180 m)Length150 mi (240 km)Disc...

Part of a series on theMilitary of ancient Rome 753 BC – AD 476 Structural history Army Unit types and ranks Decorations and punishments Legions Auxilia Generals Navy Fleets Admirals Campaign history Wars and battles Technological history Military engineering Castra Siege engines Triumphal arches Roads Political history  Strategy and tactics Infantry tactics Frontiers and fortifications Limes Walls Limes Britannicus Antonine Wall Hadrian's Wall Saxon Shore Limes Germanicus Alb Limes L...

 

For the album by Radiator, see Radiator (Radiator album). 1997 studio album by Super Furry AnimalsRadiatorStudio album by Super Furry AnimalsReleased25 August 1997Recorded1997GenreAlternative rock[1]neo-psychedelia[2]Length46:54LabelCreationProducerGorwel Owen, Super Furry AnimalsSuper Furry Animals chronology Fuzzy Logic(1996) Radiator(1997) Ice Hockey Hair(1998) Singles from Radiator Hermann ♥'s PaulineReleased: 12 May 1997 The International Language of ScreamingR...