柴廷常數

计算机科学中的算法信息论柴廷常数柴廷欧米茄数[1]停机的概率是一个实数,非正式地来讲,所表示的是随机的程式将会停止的概率。这些数字是从一個格雷戈里·柴廷製作的構造。

尽管有无穷多个停止的概率(每个方法的程式编码都各有一个),使用字母 代表他们是很普通的。因为 取决于程序编码使用的程式,这有时被称为柴廷構造,而不是柴廷常数当没有参考任何特定的编码的时候。

每个停止的概率是一个正规数超越数的实数,而不是可计算数,这意味着,没有演算法计算他的位数。事实上,每个停止的概率是马丁-洛夫随机的,意味着甚至没有任何的演算法是可以可靠地猜测他的位数的。

背景

停止的概率的定义依赖于无字首的图灵完备的可计算函数的存在。这样的函数,直观地说,代表了一种编程语言具有這樣的性質:没有有效的程式可以被获得为另一个有效的程式的部分扩展。

假设 是一个部分函数,需要一个参数跟一个有限的二元串,并有可能返回一个二元串作为输出。这个函数被称为可计算的,如果有一个图灵机有计算出他(在这个意义上:对于任何有限的二元串 若且唯若这个图灵机停止且在他的地带当给出输入的时候).

函数被称为图灵完备,如果拥有下列性質:对于一个单一的变量的每个可计算函数 ,都有一串使得对於所有的, ;这里   表示两个二元串的串接. 这意味着:可用于模拟一个变量的任何一个可计算函数。非正式地说,表示可计算函数的「腳本」,另外表示一个"解释"解析脚本作为前缀的其输入和随后执行它其余的输入。

定义域是所有输入的集合。对于图灵完备的,这样的通常可以被看到作为程式部分和数据部分的连接,并作为函数的单一程式。

函数被称为无字首如果没有两个元素 , 在其定义域使得的一个部分扩展,換句話說,的定义域是一个前置码(瞬间代码)在有限二元串的集合。一个简单的方法來强制执行「无字首性」是使用机器,这些机器的输入是一个二流从哪位可以读一个在一段时间。 没有结束的标记;结束的输入确定通过时这个图灵完备的机器决定将停止阅读更多位数。在这里,之间的差别这两个概念的程序中提到的最后一段变得清楚的;一个是很容易地认识到一些文法,而其他需要任意的计算到承认。

任何图灵完备的可计算函数的定义域都是递归可枚举集合,但是不是递归集合. 这个定义域是图灵等同停机问题.

定义

是无字首的图灵完备的可计算函数的定义域,常数被定义为

,

表示的字串的长度。这是一个无限和, 其中有一个加数对於的定义域中的每個。这要求该定义域是无字首的,再配合克拉夫特不等式,确保这个和会收敛到0到1之间的一个实数。如果是明確的,则可以被简单地写为,虽然不同的无字首的图灵完备的可计算函数会有不同的值。

与停机问题的关系

知道的(二进制的)前位数,我们可以计算出每个不超过个字元的程式的 停机问题 。假设程式其停机问题是要解决个字元的程式。在衔接时,所有长度的所有程式都在运行,直到足够的程式贡献了足够的机率,以与这些「前位数」相配。如果程式并没有停止,那么它永远也不会,因为它的贡献停止的概率将影响的第位。因此,制止的问题(对於)将得到解决。

因为有很多悬而未决的数论问题,例如哥德巴赫猜想,相当于解决特别程式(这基本上就是搜索反例,如果有一个反例发现就停止)的停机问题,知道了柴廷常数的足够位数还将意味着知道这些问题的答案。但是,由於停机问题一般並不是可以解决的,因此计算柴廷常数的任意位数是不可能的,这只是把困难的问题变成不可解決的问题,就像在试图建立一个預言机一樣。

解释作为一个机率

康托空间是所有0跟1的无限序列的集合,一个停机的概率可被解释为的测度的特定子集的康托空间在通常的概率衡量在康托空间。它是从这一解释,终止的概率取他们的名字。

该概率的测度在康托空间,有时也称为公平的硬币措施,定义,以便为任何二元字串的组序列的开头具有测量. 这意味着为每个自然的数量,该组序列的在坎特的空间,这样 测量的和本组序列的个元素是0还有衡量的

是无字首的图灵完备的的可计算函数,的定义域包括一个二元字串的无限集合

.

这些字符串中的每一个確定了康托空间的一个子集 该组包含康托空间的所有從开始的序列这些都是分离的,因为为无字首的集合, 总和

表示该集合的测度

.

在这种方式, 表示的概率是随机选择的无限的0跟1的序列以F的定义域裡的一位字串(的某个有限的长度)開始,由于这个原因,被称为停机的概率。

性質

每个柴廷常数 具有以下性質:

  • 它是算法随机(也称为马丁-洛夫随机或1-随机)。[2] 这意味着!最短的程式输出的第 位的 必须的时间至少为 n-O(1)。 这是因为,作为在哥德巴赫的例子,这些 位数使我们能够找出到底哪些最多个字元的程式将会停止。
  • 它是一个正规数,这意味着,其位数出現机率都一樣,就如同他们是用「扔一个公正的硬币」來产生的。
  • 它不是一个可计算数;没有可计算的函数能计算出它的值、列举它的二进制的所有位数,如下文所讨论的。
  • 有理数使得的 」的集合是递归可枚举集合;[3]递归理论,一个有这種性質的实数称为 左-c。e. 实数 .
  • 「有理数使得」的集合不是递归可枚举的。 (原因是:每一个有这種性質的左-c。e. 实数都是可计算的,但是这个 并不是。)
  • 是一个 算术数.
  • 这是图灵等同停止的问题,因此是在阶算术阶层.

并不是每个图灵等同于停机问题的集合都是停止的概率。 一个等价关系,索罗维等同,可以用来描绘制止的概率之间的左-c。e.实数 。[4] 我们可以显示:一个在[0,1]裡的实数是一个柴廷常数(即停止的概率的某些无字首的图灵完备的的可计算函数)若且唯若如果它是左-c。e. 並且是算法随机。 Ω 是少数几个 可定义的 算法随机数,它是最着名的算法随机数,但它根本不是典型的算法随机数。[5]

不可计算性

一个实数是可计算的,如果有一个算法,给出,返回该数的前个位数。 这相当于存在一个程式,能夠列举数字的所有位数。

没有停机的概率是可计算的。 证明这一事实依赖于一种算法,给出的前个位数,解决图灵的停机问题对於长度不超過的程式。由于停机问题是不可判定问題,沒有办法被计算出來。

算法进行如下。 给出 的前n个位数,以及数字,这个算法枚举了的定义域,直到这个定义域裡足够的元素已经被找到,使他们所代表的概率是. 在这一点后,没有长度的附加程式可以在定义域裡,因为每个程式将增加到这个措施,这是不可能的。因此,长度的字串的集合在这个定义域中就是「已经一一列举的字串的集合」。

算法的随机性

一个真正的数量是随机的,如果二进制序列代表实际数量是一个 算法的随机序列. 卡路德、赫特凌,寇賽諾夫 以及 王 表明,[6] 这一递归的实数是一个算法随机的序列,若且唯若它是一个柴廷 数。

柴廷ΩU

柴廷常數是指停機的概率,通常不是可計算數,且有無窮多個停止的概率(每個方法的程式編碼都各有一個)。其中一種通用圖靈機的停機概率由卡盧德(Calude)等人計算並給出數值,約為0.007875[7][1]

0.00787499699...(OEIS數列A100264

停机问題的不完备定理

对于每一个的一致有效的代表自然数的公理系统,如皮亚诺公理,存在常数使得没有「 位数 之後的位数」可以被证明为1或0,在这个系統。常数取决于形式系统是有效地代表,并因此并不直接反映的复杂性不言自明的系统。这个不完整的结果是类似于哥德尔不完备定理在于,它表明,没有一致的正式理论运算可以完成。

参见

参考文献

  1. ^ 1.0 1.1 Weisstein, Eric W. (编). Chaitin's Constant. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2012-05-28]. (原始内容存档于2020-11-11) (英语). 
  2. ^ Downey/Hirschfeld, Theorem 6.1.3
  3. ^ Downey/Hirschfeld, Theorem 5.1.11
  4. ^ Downey/Hirschfeldt, p.405
  5. ^ Downey/Hirschfeld, p.228-229
  6. ^ Calude, Hertling, Khoussainov, and Wang. Recursively enumerable reals and Chaitin's Ω numbers (PDF). Theoretical Computer Science. 2001, 255: 125–149. (原始内容 (PDF)存档于2021-01-22). 
  7. ^ Calude, C. S.; Dinneen, M. J.; Shu, C.-K. Computing a Glimpse of Randomness (PDF). Exper. Math. 2002, 11: 361–370 [2022-09-29]. (原始内容存档 (PDF)于2022-10-18). 

Read other articles:

Keuskupan Saint-ÉtienneDioecesis Sancti StephaniDiocèse de Saint-ÉtienneKatolik Katedral Saint-ÉtienneLokasiNegara PrancisProvinsi gerejawiLyonStatistikLuas3.035 km2 (1.172 sq mi)Populasi- Total- Katolik(per 2014)591.628464,000 (perkiraan) (78.4%)InformasiDenominasiKatolik RomaGereja sui iurisGereja LatinRitusRitus RomaPendirian26 Desember 1970KatedralKatedral Santo Karolus Boromeus di Saint-ÉtiennePelindungSanto StefanusKepemimpinan kiniPausFransi...

 

General Motors Specialty VehiclesIndustriOtomotifPendahuluHSVDidirikan19 Agustus 2020Wilayah operasiAustralia dan Selandia BaruMerekChevrolet dan GMCDivisiGeneral MotorsSitus webhttps://www.gmspecialtyvehicles.com General Motors Specialty Vehicles (GMSV) adalah usaha General Motors yang baru diluncurkan yang beroperasi di Australia dan Selandia Baru. Di GMSV, kami hanya memilih kendaraan GM paling ikonik untuk diberikan kepada pelanggan kami yang ingin memiliki sesuatu yang benar-benar istime...

 

Alfred LoewensteinLoewenstein (oleh Jos De Swerts, 1926)LahirAlfred Léonard Loewenstein(1877-03-11)11 Maret 1877BrusselsMeninggal4 Juli 1928(1928-07-04) (umur 51)Laut UtaraPekerjaanbankir, wirausahawan Alfred Léonard Loewenstein CB (11 Maret 1877 – 4 Juli 1928)[1] adalah seorang pemodal asal Belgia. Pada puncaknya pada 1920an, ia memiliki kekayaan sekitar £12 juta, menjadikannya orang terkaya ketiga di dunia pada masanya. Publikasi William Norris: The Man Who ...

بورما وتعرف أيضاً باسم ميانمار، ورسمياً جمهورية اتحاد ميانمار بورمية: Myanmar long form.svg. هي احدي دول جنوب شرق آسيا. في 1 أبريل 1937 انفصلت عن حكومة الهند البريطانية نتيجة اقتراع بشأن بقائها تحت سيطرة مستعمرة الهند البريطانية أو استقلالها لتكون مستعمرة بريطانية منفصلة، حيث كانت إح...

 

State in southern Greece (1205–1458) For the opera, see The Duchess of Athens. Duchy of AthensΔουκᾶτον Ἀθηνῶν (Greek)Ducat d'Atenes (Catalan)1205–1458 Arms of the Duchy under the de la Roche family The Lordship of Athens and the other Greek and Latin states of southern Greece, c. 1210StatusVassal state[a] of various countries, de facto autonomousCapitalAthens, ThebesCommon languagesFrench (until 1311) Catalan (1311–88) Greek (popularly and officia...

 

Questa voce sugli argomenti arene di pallacanestro e palazzetti di pallavolo è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Ginásio do MaracanãzinhoMaracanãzinho, Ginásio Gilberto Cardoso Informazioni generaliStato Brasile UbicazioneRua Professor Rabelo20271-111 Rio de Janeiro Inizio lavori24 settembre 1954 Inaugurazione1954 Chiusuraottobre 2003 Ristrutturazione2003-2007 Costi di ricostr.R$ 97 000 000 ProprietarioSoprintendenza del...

EnglandAssociationEnglish Lacrosse AssociationConfederationELF (Europe)World CupAppearances10 (first in 1982)Best resultRunner-ups (1989, 1993)Websitewww.englandlacrosse.co.uk The England women's national lacrosse team represents England at women's lacrosse. It is governed by the English Lacrosse Association. They were runners-up in the Women's Lacrosse World Cup twice, and have also hosted the tournament twice. The team came 3rd in the 2017 Women's Lacrosse World Cup, which has held in Osha...

 

Brazilian football manager and former player This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Jair Pereira Brazilian footballer – news · newspapers · books · scholar · JSTOR (December 2012) ...

 

Administrative entry restrictions An Armenian passport Visa requirements for Armenian citizens are administrative entry restrictions by the authorities of other states placed on citizens of Armenia. As of January 2024, Armenian citizens had visa-free or visa on arrival access to 69 countries and territories, ranking the Armenian passport 75th in terms of travel freedom according to the Henley Passport Index.[1] Visa requirements map Visa requirements for Armenian citizens holding ordi...

Main railway line in south-east England Chatham Main LineSoutheastern Class 465/9 Networker at Chatham in 2015OverviewStatusOperationalOwnerNetwork RailLocaleGreater LondonSouth East EnglandTerminiLondon VictoriaRamsgateDover PrioryStations40ServiceTypeCommuter rail, Heavy railSystemNational RailOperator(s)SE TrainsThameslinkDepot(s)Gillingham EMUD, Ramsgate EMUD, Grovesnor Carriage ShedRolling stockClass 375 ElectrostarClass 377 ElectrostarClass 395 JavelinClass 465 Networker Class 466 Netwo...

 

For rallies prior to the 2016 presidential elections, see List of rallies for the 2016 Donald Trump presidential campaign. This article is part of a series aboutDonald Trump Business and personal Business career The Trump Organization wealth tax returns Media career The Apprentice bibliography filmography Eponyms Family Foundation American football Golf Honors Public image in popular culture SNL parodies handshakes Legal affairs Sexual misconduct allegations Nicknames pseudonyms Racial views...

 

Historic neighborhood of Honolulu, Hawaii United States historic placeChinatown Historic DistrictU.S. National Register of Historic PlacesU.S. Historic district Historic Wo Fat restaurant building (built 1938), at the corner of Hotel and MaunakeaLocationBeretania Street, Nuuanu Stream, Nuuanu Avenue, and Honolulu Harbor, Honolulu, HawaiiCoordinates21°18′44″N 157°51′46″W / 21.31222°N 157.86278°W / 21.31222; -157.86278Area36 acres (15 ha)Built1900NRHP...

Port authority in the United Kingdom Port of London AuthorityLogoFormer headquarters, Tower HillPredecessorThames ConservancyLondon and India Docks CompanySurrey Commercial Docks CompanyMillwall Dock CompanyFormation31 March 1909; 115 years ago (1909-03-31)[1]TypePublic trustPurposeOperation of the Port of LondonHeadquartersLondon River HouseLocationGravesendCoordinates51°26′41″N 0°22′26″E / 51.4447°N 0.3740°E / 51.4447; 0.3740Regi...

 

Head of state of Myanmar 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: President of Myanmar – news · newspapers · books · scholar · JSTOR (March 2021) (Learn how and when to remove this message) President of theRepublic of the Union of Myanmarပြည်ထောင်စု သမ္မတ မြန်�...

 

VùngCòn gọi là:Government Office RegionThể loạiVùng thống kêVùng hành chính (1)Vị tríAnh QuốcThành lập1994Số lượng còn tồn tại9 (tính đến 2010)Tình trạng thêmVùng cấp một AnhKhu vực bầu cử Nghị viện châu ÂuDân số2.5–8 triệuDiện tích1.000–23.000 km²Hình thức chính quyềnHội đồng lãnh đạo chính quyền địa phương (6)Hội đồng được bầu (1)không (2)Đơn vị hành chính thấp hơnhạt không...

Danemark aux Jeux olympiques d'hiver de 1964 Code CIO DEN Comité Comité national olympique danois Lieu Innsbruck Participation 4e aux Jeux d'hiver Athlètes 2 hommes Porte-drapeau Svend Carlsen (en) MédaillesRang : Or0 Arg.0 Bron.0 Total0 Danemark aux Jeux olympiques d'hiver Danemark aux Jeux olympiques d'hiver de 1960 Danemark aux Jeux olympiques d'hiver de 1968 modifier  Le Danemark participe aux Jeux olympiques d'hiver de 1964, organisés à Innsbruck en Autriche. Ce pays pre...

 

Village in Estonia Village in Tartu County, EstoniaLaheperaVillageCountry EstoniaCountyTartu CountyParishPeipsiääre ParishTime zoneUTC+2 (EET) • Summer (DST)UTC+3 (EEST) Lahepera is a small farming village in Peipsiääre Parish, Tartu County in eastern Estonia.[1] References ^ Classification of Estonian administrative units and settlements 2014[dead link] (retrieved 28 July 2021) External links Weather in Lahepera vteSettlements in Peipsiääre ParishTown K...

 

Pour les autres membres de la famille, voir Famille Della Rovere. Jules II Portrait du pape Jules II peint par Raphaël. 1511. National Gallery. Londres Biographie Nom de naissance Giuliano della Rovere Naissance 5 décembre 1443Albisola, République de Gênes Père Raffaello della Rovere (en) Mère Teodora Marinola (d) Ordre religieux Ordre des Frères mineurs de saint François Décès 21 février 1513 (à 69 ans)Rome,  États pontificaux Pape de l'Église catholique Élection au...

У этого топонима есть и другие значения, см. Гузерипль. ПосёлокГузерипльадыг. Гъузэрыплъ 43°59′46″ с. ш. 40°08′06″ в. д.HGЯO Страна  Россия Субъект Федерации Адыгея Муниципальный район Майкопский Сельское поселение Даховское История и география Высота центра 65...

 

Spanish Navy officer and politician (1821–1885) You can help expand this article with text translated from the corresponding article in Spanish. (December 2009) Click [show] for important translation instructions. View a machine-translated version of the Spanish article. 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-pa...