Chaitin's constant (original) (raw)
En complexitat computacional, la constant de Chaitin o nombre Omega de Chaitin o probabilitat de parada és, de forma informal, la probabilitat de que un programa escrit al atzar aturi correctament una màquina de Turing determinista. En ser una probabilitat, ha de ser un nombre real entre 0 i 1. Aquest nombre va ser definit per Gregory Chatitin
| Property | Value |
|---|---|
| dbo:abstract | En complexitat computacional, la constant de Chaitin o nombre Omega de Chaitin o probabilitat de parada és, de forma informal, la probabilitat de que un programa escrit al atzar aturi correctament una màquina de Turing determinista. En ser una probabilitat, ha de ser un nombre real entre 0 i 1. Aquest nombre va ser definit per Gregory Chatitin (ca) Chaitinovo číslo, Ω, někdy také Chaitinova konstanta, je matematická konstanta definovaná Součet je veden přes všechny konečné posloupnosti 0 a 1 takové, že univerzální Turingův stroj pro danou posloupnost na vstupu zastaví; je délka .Z Kraftovy nerovnosti plyne, že suma je omezená a tedy dokazatelně konverguje k reálnému číslu, pro nějž platí . Toto reálné číslo však nelze žádným algoritmem spočítat s přesností vyšší než striktně daný počet binárních míst; speciálně pak neexistuje algoritmus schopný hodnotu Chaitinova čísla libovolně aproximovat. Znalost hodnoty s dostatečnou přesností by totiž řešila problém zastavení, o němž Alan Turing dokázal, že je algoritmicky neřešitelný. Chaitinovo číslo je tedy reálné číslo, pro nějž je matematicky dokazatelné, že jej nebudeme umět nikdy spočítat ani se k jeho hodnotě přiblížit nad určitou mez přesnosti. (cs) Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält. ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als wobei die Summe über alle haltenden Programme gemeint ist (alle Programme, die ohne Eingabe nach endlicher Laufzeit halten) und die Länge des Programms in Bit bezeichnet. Das bedeutet also, dass jedes haltende Programm der Länge m Bit das m-te Bit der Binärdarstellung von um 1 erhöht. Bemerkung: Da es gewisse Freiheiten gibt, universelle Turingmaschinen zu definieren, hängt der genaue Wert der Konstante von der gewählten Maschinendefinition ab. Durch Kenntnis der ersten n Bit der Konstante lässt sich das Halteproblem für bis zu n Bit lange Programme entscheiden, sodass sich durch genaue Kenntnis der ersten paar tausend Bit der Konstante viele interessante Probleme der Mathematik lösen ließen. Da das Halteproblem aber nicht lösbar ist, kann nicht berechenbar sein und ist also eine transzendente reelle Zahl. Eine Forschergruppe um Cristian Calude von der Universität Auckland bestimmte im Jahr 2002 durch Überprüfen aller Turingprogramme von bis zu 80 Bit Länge die ersten 64 Bit der Zahl. (de) In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin. Although there are infinitely many halting probabilities, one for each method of encoding programs, it is common to use the letter Ω to refer to them as if there were only one. Because Ω depends on the program encoding used, it is sometimes called Chaitin's construction when not referring to any specific encoding. Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits. (en) La constante de Chaitin (o número omega de Chaitin o probabilidad de parada) es la probabilidad de que un programa elegido al azar detenga correctamente una máquina de Turing determinada. Al ser una probabilidad ha de ser un número entre 0 y 1. Sea P el conjunto de todos los programas que se detienen, y |p |
| dbo:wikiPageExternalLink | http://www.plus.maths.org.uk/issue37/features/omega/index.html https://web.archive.org/web/20160211170316/https:/www.cs.auckland.ac.nz/~chaitin/sciamer3.html https://arxiv.org/abs/1707.08109 http://citeseer.ist.psu.edu/li97introduction.html http://www.idsia.ch/~juergen/kolmogorov.html http://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf |
| dbo:wikiPageID | 6205 (xsd:integer) |
| dbo:wikiPageLength | 17586 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122124621 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Algorithmic_information_theory dbc:Algorithmic_information_theory dbc:Real_transcendental_numbers dbr:Peano_axioms dbr:Universal_Turing_Machine dbr:Universality_probability dbr:Definable_real_number dbr:Dovetailing_(computer_science) dbr:Computable_function dbr:Concatenation dbr:Measure_theory dbr:Oracle_machine dbr:Enumerable dbr:Arithmetical_hierarchy dbr:Computable_number dbr:Computable_set dbr:Computably_enumerable_set dbr:Computer_science dbr:Partial_function dbr:Transcendental_number dbr:Domain_of_a_function dbr:Jürgen_Schmidhuber dbr:Algorithmically_random_sequence dbr:Equivalence_relation dbr:Normal_number dbr:Formal_system dbr:Goldbach's_conjecture dbr:Kolmogorov_complexity dbr:Probability dbr:Random dbr:Gregory_Chaitin dbr:Gödel's_incompleteness_theorem dbr:Halting_problem dbc:Theory_of_computation dbr:Axiomatic_system dbr:Natural_numbers dbr:Cantor_space dbr:Rational_number dbr:Real_number dbr:Turing_machine dbr:Series_(mathematics) dbr:Undecidable_problem dbr:Kraft's_inequality dbr:Turing_jump dbr:Probability_measure dbr:Turing_degree dbr:Limit-computable dbr:Arithmetical_number dbr:Incompleteness_theorem dbr:Recursion_theory dbr:Algorithmic_randomness dbr:Computational_universality dbr:Binary_string dbr:Prefix-free_code |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Main dbt:More_footnotes dbt:Redirect dbt:Sfn dbt:Short_description dbt:Snd dbt:Use_dmy_dates dbt:Irrational_number |
| dcterms:subject | dbc:Algorithmic_information_theory dbc:Real_transcendental_numbers dbc:Theory_of_computation |
| gold:hypernym | dbr:Number |
| rdf:type | yago:WikicatMathematicalConstants yago:WikicatTranscendentalNumbers yago:Abstraction100002137 yago:Cognition100023271 yago:ComplexNumber113729428 yago:Concept105835747 yago:Constant105858936 yago:Content105809192 yago:DefiniteQuantity113576101 yago:Idea105833840 yago:IrrationalNumber113730584 yago:Measure100033615 yago:Number113582013 yago:PsychologicalFeature100023100 yago:Quantity105855125 yago:RealNumber113729902 yago:TranscendentalNumber113730756 |
| rdfs:comment | En complexitat computacional, la constant de Chaitin o nombre Omega de Chaitin o probabilitat de parada és, de forma informal, la probabilitat de que un programa escrit al atzar aturi correctament una màquina de Turing determinista. En ser una probabilitat, ha de ser un nombre real entre 0 i 1. Aquest nombre va ser definit per Gregory Chatitin (ca) La constante de Chaitin (o número omega de Chaitin o probabilidad de parada) es la probabilidad de que un programa elegido al azar detenga correctamente una máquina de Turing determinada. Al ser una probabilidad ha de ser un número entre 0 y 1. Sea P el conjunto de todos los programas que se detienen, y |p |
| rdfs:label | Constant de Chaitin (ca) Chaitinovo číslo (cs) Chaitinsche Konstante (de) Constante de Chaitin (es) Chaitin's constant (en) Oméga de Chaitin (fr) Costante di Chaitin (it) 차이틴 상수 (ko) チャイティンの定数 (ja) Constante de Chaitin (pt) Константа Хайтина (ru) Chaitins konstant (sv) 柴廷常數 (zh) |
| owl:sameAs | freebase:Chaitin's constant yago-res:Chaitin's constant wikidata:Chaitin's constant dbpedia-ca:Chaitin's constant dbpedia-cs:Chaitin's constant dbpedia-de:Chaitin's constant dbpedia-es:Chaitin's constant dbpedia-fr:Chaitin's constant dbpedia-it:Chaitin's constant dbpedia-ja:Chaitin's constant dbpedia-ko:Chaitin's constant dbpedia-pt:Chaitin's constant dbpedia-ru:Chaitin's constant dbpedia-sv:Chaitin's constant dbpedia-zh:Chaitin's constant https://global.dbpedia.org/id/4uNk5 |
| prov:wasDerivedFrom | wikipedia-en:Chaitin's_constant?oldid=1122124621&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Chaitin's_constant |
| is dbo:knownFor of | dbr:Gregory_Chaitin |
| is dbo:wikiPageRedirects of | dbr:Chaitin_constant dbr:Chaitins_constant dbr:Halting_probability dbr:Chaitin's_Omega dbr:Chaitin's_constant_Ω dbr:Chaitin's_construction dbr:Chaitin's_number dbr:Chaitin's_omega dbr:Chaitin_Omega dbr:Chaitin_omega dbr:Chaitin’s_Ω dbr:Omega_(computer_science) dbr:Omega_number |
| is dbo:wikiPageWikiLink of | dbr:Algorithmic_information_theory dbr:List_of_mathematical_constants dbr:List_of_numbers dbr:List_of_scientific_constants_named_after_people dbr:Universality_probability dbr:Definable_real_number dbr:List_of_letters_used_in_mathematics_and_science dbr:Computable_function dbr:Mathematical_constant dbr:Omega dbr:Omega_(disambiguation) dbr:Computable_number dbr:Computation_in_the_limit dbr:Kraft–McMillan_inequality dbr:Transcendental_number dbr:K-trivial_set dbr:List_of_Bronx_High_School_of_Science_alumni dbr:Algorithmically_random_sequence dbr:Normal_number dbr:Kolmogorov_complexity dbr:Randomness dbr:Gregory_Chaitin dbr:Halting_problem dbr:Iota_and_Jot dbr:Hypercomputation dbr:Chaitin_constant dbr:Chaitins_constant dbr:Turing_machine dbr:Yongge_Wang dbr:Halting_probability dbr:Chaitin's_Omega dbr:Chaitin's_constant_Ω dbr:Chaitin's_construction dbr:Chaitin's_number dbr:Chaitin's_omega dbr:Chaitin_Omega dbr:Chaitin_omega dbr:Chaitin’s_Ω dbr:Omega_(computer_science) dbr:Omega_number |
| is dbp:knownFor of | dbr:Gregory_Chaitin |
| is foaf:primaryTopic of | wikipedia-en:Chaitin's_constant |