Chaitin's constant
http://dbpedia.org/resource/Chaitin's_constant an entity of type: WikicatMathematicalConstants
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
rdf:langString
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| el tamaño en bits de un programa p, Ω está definida de la siguiente manera:
rdf:langString
La costante di Chaitin o numero di Chaitin (indicato con la lettera greca Ω) è un numero reale che rappresenta la probabilità di terminazione di un programma costruito casualmente. Introdotto da Gregory Chaitin, Ω è un numero normale e trascendente, ma non è un numero computabile.
rdf:langString
에서 차이틴 상수(Chaitin's constant) 또는 차이틴 오메가 수(Chaitin omega number) 또는 정지 확률은 무작위로 만들어진 프로그램이 정지할 확률을 나타내는 실수이다. 그레고리 차이틴이 정의하였다. 무작위로 만든 프로그램이 정지할 확률은 프로그램을 0과 1로 부호화하는 방식에 따라 달라진다. 따라서 무한히 많은 종류의 ‘정지 확률’이 존재하지만, 마치 단 하나만 존재하는 것처럼 취급하고 그리스 글자 오메가(Ω)로 나타내는 경우가 많다. 특정한 부호화 방식을 염두에 둔 것이 아닐 때에는 상수라는 이름 대신 차이틴 구성(Chaitin's construction)이라는 이름을 사용하기도 한다. 각각의 정지 확률은 초월수이고 정규수이며, 계산 불가능한 수이다. 계산 불가능하다는 것은 그 값을 임의의 정확도로 계산하는 알고리즘이 존재할 수 없다는 뜻이다. 나아가 각각의 정지 확률은 이다.
rdf:langString
チャイティンの定数（チャイティンのていすう、英: Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、英: Halting probability）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。 個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。
rdf:langString
在计算机科学中的算法信息论，柴廷常数（柴廷欧米茄数）或停机的概率是一个实数，非正式地来讲，所表示的是随机的程式将会停止的概率。这些数字是从一個格雷戈里·柴廷製作的構造。 尽管有无穷多个停止的概率（每个方法的程式编码都各有一个），使用字母 Ω 代表他们是很普通的。因为 Ω 取决于程序编码使用的程式，这有时被称为柴廷構造，而不是柴廷常数当没有参考任何特定的编码的时候。 每个停止的概率是一个正规数和超越数的实数，而不是可计算数，这意味着，没有演算法计算他的位数。事实上，每个停止的概率是马丁-洛夫随机的，意味着甚至没有任何的演算法是可以可靠地猜测他的位数的。
rdf:langString
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ý.
rdf:langString
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. 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.
rdf:langString
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.
rdf:langString
En théorie algorithmique de l'information, une constante Oméga de Chaitin (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d'être aléatoire et de ne pas être calculable au sens de Turing : un algorithme donné ne permet de calculer qu'un nombre fini de ses décimales. Jusqu'à la définition de ce nombre, il n'existait pas d'exemple mathématiquement précis et « concret » de suite aléatoire.
rdf:langString
Em ciência da computação, na sub-área de teoria da informação algorítmica, a constante de Chaitin (número Ômega de Chaitin) ou probabilidade de parada é um número real que informalmente representa a probabilidade de que um programa construído de forma aleatória irá parar. Estes números são formados de uma construção de Gregory Chaitin.
rdf:langString
I beräkningsteori är Chaitins konstant, Ω, ett tal som representerar sannolikheten för att ett slumpmässigt sammansatt datorprogram terminerar. Mer precist finns oändligt många olika Chaitins konstanter, en för varje eller programspråk. Konceptet studerades ursprungligen av . Calude, Dinneen och Shu har bestämt de första 64 bitarna av Chaitins konstant för en viss beräkningsmodell. De är 0,00000 01000 00010 00001 10001 00001 10100 01111 11001 01110 11101 00001 0000... vilket motsvarar decimaltalet 0,00787 49969 97812 3844...
rdf:langString
В разделе информатики — алгоритмической теории информации, константа Хайтина или вероятность остановки — вещественное число, которое, неформально говоря, является вероятностью того, что произвольно выбранная программа остановится. Существование таких чисел было продемонстрировано Грегори Хайтином. Всякое Ω является нормальным трансцендентным числом, которое определимо, но невычислимо, что означает отсутствие алгоритма, который перечислял бы его цифры.
rdf:langString
rdf:langString
Constant de Chaitin
rdf:langString
Chaitinovo číslo
rdf:langString
Chaitinsche Konstante
rdf:langString
Constante de Chaitin
rdf:langString
Chaitin's constant
rdf:langString
Oméga de Chaitin
rdf:langString
Costante di Chaitin
rdf:langString
차이틴 상수
rdf:langString
チャイティンの定数
rdf:langString
Constante de Chaitin
rdf:langString
Константа Хайтина
rdf:langString
Chaitins konstant
rdf:langString
柴廷常數
xsd:integer
6205
xsd:integer
1122124621
rdf:langString
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
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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| el tamaño en bits de un programa p, Ω está definida de la siguiente manera:
rdf:langString
En théorie algorithmique de l'information, une constante Oméga de Chaitin (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d'être aléatoire et de ne pas être calculable au sens de Turing : un algorithme donné ne permet de calculer qu'un nombre fini de ses décimales. Jusqu'à la définition de ce nombre, il n'existait pas d'exemple mathématiquement précis et « concret » de suite aléatoire. Techniquement, il est défini comme étant la probabilité qu’un programme auto-délimité, généré aléatoirement, finisse par s'arrêter. Les programmes en question sont associés à une machine de Turing universelle ou à un modèle de calcul donné. Il existe donc une infinité de constantes de Chaitin, chacune associée soit à une machine de Turing universelle donnée, soit à un modèle de calcul. Cette définition permet également de coder, sous la forme la plus compacte possible, la solution du problème de l'arrêt pour tous les programmes d'un modèle de calcul donné. Comme il est possible de traduire la plupart des problèmes mathématiques en termes de programme informatique qui s'arrête ou non, la connaissance d'un nombre Oméga permet — en principe — de démontrer un grand nombre de théorèmes ou de conjectures mathématiques, dont certains encore non résolus à ce jour comme l'hypothèse de Riemann. Ces nombres apportent un éclairage sur l'incomplétude des mathématiques, mise au jour par le célèbre théorème de Gödel, ainsi que des éléments d'appréciation en ce qui concerne sa signification et sa portée.
rdf:langString
La costante di Chaitin o numero di Chaitin (indicato con la lettera greca Ω) è un numero reale che rappresenta la probabilità di terminazione di un programma costruito casualmente. Introdotto da Gregory Chaitin, Ω è un numero normale e trascendente, ma non è un numero computabile.
rdf:langString
에서 차이틴 상수(Chaitin's constant) 또는 차이틴 오메가 수(Chaitin omega number) 또는 정지 확률은 무작위로 만들어진 프로그램이 정지할 확률을 나타내는 실수이다. 그레고리 차이틴이 정의하였다. 무작위로 만든 프로그램이 정지할 확률은 프로그램을 0과 1로 부호화하는 방식에 따라 달라진다. 따라서 무한히 많은 종류의 ‘정지 확률’이 존재하지만, 마치 단 하나만 존재하는 것처럼 취급하고 그리스 글자 오메가(Ω)로 나타내는 경우가 많다. 특정한 부호화 방식을 염두에 둔 것이 아닐 때에는 상수라는 이름 대신 차이틴 구성(Chaitin's construction)이라는 이름을 사용하기도 한다. 각각의 정지 확률은 초월수이고 정규수이며, 계산 불가능한 수이다. 계산 불가능하다는 것은 그 값을 임의의 정확도로 계산하는 알고리즘이 존재할 수 없다는 뜻이다. 나아가 각각의 정지 확률은 이다.
rdf:langString
チャイティンの定数（チャイティンのていすう、英: Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、英: Halting probability）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。 個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。
rdf:langString
В разделе информатики — алгоритмической теории информации, константа Хайтина или вероятность остановки — вещественное число, которое, неформально говоря, является вероятностью того, что произвольно выбранная программа остановится. Существование таких чисел было продемонстрировано Грегори Хайтином. Хотя существует бесконечное множество вероятностей остановки, обычно используют букву Ω для обозначения их всех, как если бы существовало только одно такое число. Так как численное значение Ω зависит от используемого языка программирования, то если не ссылаются на какой-то определённый язык, её часто называют построением Хайтина, а не константой Хайтина. Всякое Ω является нормальным трансцендентным числом, которое определимо, но невычислимо, что означает отсутствие алгоритма, который перечислял бы его цифры.
rdf:langString
I beräkningsteori är Chaitins konstant, Ω, ett tal som representerar sannolikheten för att ett slumpmässigt sammansatt datorprogram terminerar. Mer precist finns oändligt många olika Chaitins konstanter, en för varje eller programspråk. Konceptet studerades ursprungligen av . Chaitins konstant är ett och transcendent tal. Dess mest anmärkningsvärda egenskap är att det är men trots det oberäkningsbart. Anledningen är att en algoritm som har tillgång till de första n bitarna av Ω skulle kunna lösa stopproblemet för n bitar långa program, men stopproblemet är olösbart och därmed kan Ω inte beräknas för tillräckligt stora n. Calude, Dinneen och Shu har bestämt de första 64 bitarna av Chaitins konstant för en viss beräkningsmodell. De är 0,00000 01000 00010 00001 10001 00001 10100 01111 11001 01110 11101 00001 0000... vilket motsvarar decimaltalet 0,00787 49969 97812 3844...
rdf:langString
Em ciência da computação, na sub-área de teoria da informação algorítmica, a constante de Chaitin (número Ômega de Chaitin) ou probabilidade de parada é um número real que informalmente representa a probabilidade de que um programa construído de forma aleatória irá parar. Estes números são formados de uma construção de Gregory Chaitin. Apesar de haver uma infinidade de probabilidades de parada, é comum usar o símbolo Ω (ohm) para nos referirmos a elas como se fossem apenas uma. Porque Ω depende da codificação utilizada no programa, então é chamado as vezes de Construção de Chaitin ao invés de Constante de Chaitin quando não referencia nenhuma codificação específica. Cada probabilidade de parada é um número real normal e transcendente que não é computável, o que significa que não existe algoritmo para computar aqueles dígitos. De fato, cada probabilidade de parada é uma sequência aleatória de Martin-Löf, representando que não existe algoritmo algum que possa adivinhar de fato seus dígitos.
rdf:langString
在计算机科学中的算法信息论，柴廷常数（柴廷欧米茄数）或停机的概率是一个实数，非正式地来讲，所表示的是随机的程式将会停止的概率。这些数字是从一個格雷戈里·柴廷製作的構造。 尽管有无穷多个停止的概率（每个方法的程式编码都各有一个），使用字母 Ω 代表他们是很普通的。因为 Ω 取决于程序编码使用的程式，这有时被称为柴廷構造，而不是柴廷常数当没有参考任何特定的编码的时候。 每个停止的概率是一个正规数和超越数的实数，而不是可计算数，这意味着，没有演算法计算他的位数。事实上，每个停止的概率是马丁-洛夫随机的，意味着甚至没有任何的演算法是可以可靠地猜测他的位数的。
xsd:nonNegativeInteger
17586