Algorithmically random sequence (original) (raw)
アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、英: Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。
| Property | Value |
|---|---|
| dbo:abstract | Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle machine, there are different notions of randomness. The most common of these is known as Martin-Löf randomness (K-randomness or 1-randomness), but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single (finite or infinite) sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random (i.e., K-incompressible), "Martin-Löf–Chaitin random". It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an independent identically distributed equiprobable stochastic process. Because infinite sequences of binary digits can be identified with real numbers in the unit interval, random binary sequences are often called (algorithmically) random real numbers. Additionally, infinite binary sequences correspond to characteristic functions of sets of natural numbers; therefore those sequences might be seen as sets of natural numbers. The class of all Martin-Löf random (binary) sequences is denoted by RAND or MLR. (en) Intuitivamente, una secuencia algorítmicamente aleatoria (o secuencia aleatoria) es una secuencia infinita de dígitos binarios que aparece aleatoria a cualquier algoritmo. La definición no puede aplicarse igualmente bien a las secuencias en cualquier conjunto finito de caracteres, pero ingenuamente aplica en la práctica. Las secuencias aleatorias son los objetos principales de estudio en la teoría algorítmica de la información. Como los diferentes tipos de algoritmos se consideran a veces, que van desde algoritmos con límites específicos en el tiempo de recorrido a los algoritmos que pueden hacer preguntas de un oráculo, existen distintas nociones de aleatoriedad. El más común de ellos es conocido como aleatoriedad Martin-Löf (o 1-azar), pero las formas más fuertes y más débiles de la aleatoriedad también existen. El término "azar" se utiliza para referirse a una secuencia sin aclaración se toma generalmente para significar "Martin-Löf azar" (que se define más adelante). Debido a secuencias infinitas de dígitos binarios pueden ser identificados con números reales en el intervalo de unidad, secuencias aleatorias binarias son a menudo llamados números reales aleatorios. Adicionalmente, las secuencias infinitas binarios corresponden a funciones características de conjuntos de números naturales; por lo que dichas secuencias puede ser visto como un conjunto de números naturales. La clase de aleatoria de secuencias de Martin-Löf (binario) se denota por RAND o MLR. (es) アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、英: Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。 (ja) 알고리즘 무작위 수열(Algorithmic random sequence)이란 어떤 알고리즘에 대해서 각 알파벳이 무작위하게 등장한다고 간주되는 무한수열이다. 무작위 수열을 정의하는데 쓰이는 알고리즘의 종류는 매우 다양하기 때문에 무작위성에도 서로 다른 정의가 있다. 마틴-뢰프 무작위성(Martin-Löf randomnes)은 그 중 가장 흔하게 사용되는 정의이다. 무작위 수열은 의 주요한 연구주제중 하나이다. (ko) Intuitivamente, uma sequência algoritmicamente aleatória (ou 'sequência aleatória' ) é uma sequência infinita de dígitos binários que parece aleatória para qualquer algoritmo. O conceito pode ser aplicado analogamente para as sequências em qualquer alfabeto finito (por exemplo, dígitos decimais). Sequências aleatórias são objetos-chave de estudo em teoria algorítmica da informação. Como os diferentes tipos de algoritmos são considerados às vezes, variando de algoritmos com limitantes específicos sobre o seu tempo de execução para algoritmos que podem fazer perguntas de um oráculo, existem diferentes noções de aleatoriedade. O mais comum deles é conhecido como 'aleatoriedade de Martin-Löf ' (ou '1-aleatoriedade' ), mas outras formas mais fortes e mais fracas da aleatoriedade também existem. O termo "aleatório" utilizado para se referir a uma sequência sem esclarecimento é geralmente considerado como significando "aleatório Martin-Löf " (definido a seguir). Pelo fato de sequências infinitas de dígitos binários poderem ser identificadas com números reais no intervalo unitário, sequências binárias aleatórias são freqüentemente chamadas de 'números reais aleatórios' . Além disso, as sequências binárias infinitas correspondem às funções características de conjuntos de números naturais; portanto, essas sequências podem ser vistas como conjuntos de números naturais. A classe de todas as sequências aleatórias Martin-Löf (binária) é denotada por RAND ou MLR. (pt) |
| dbo:wikiPageExternalLink | http://www.cs.bu.edu/~gacs/papers/Gacs-every-seq.pdf http://www.mcs.vuw.ac.nz/math/papers/bullSep12.ps http://nbn-resolving.de/urn/resolver.pl%3Furn:nbn:de:hebis:30-20812 https://web.archive.org/web/20160202145649/http:/www.mcs.vuw.ac.nz/math/papers/bullSep12.ps http://homepages.cwi.nl/~paulv/kolmogorov.html |
| dbo:wikiPageID | 4257548 (xsd:integer) |
| dbo:wikiPageLength | 21256 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1108975092 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prefix_(computer_science) dbr:Probability_distribution dbr:Michiel_van_Lambalgen dbr:Algorithmic_information_theory dbc:Algorithmic_information_theory dbr:Per_Martin-Löf dbr:Richard_von_Mises dbr:Universality_probability dbr:Decidability_(logic) dbr:Complement_(set_theory) dbr:Computably_enumerable dbr:Concatenation dbr:Measure_(mathematics) dbr:Oracle_machine dbr:Church–Turing_thesis dbr:G-delta_set dbr:Gambling dbr:Monte_Carlo_method dbr:Arithmetical_hierarchy dbr:Leonid_Levin dbr:Stochastics dbr:Theory_of_computation dbr:Data_compression dbr:Countable dbr:K-trivial_set dbr:Lebesgue_measure dbr:Normal_number dbr:Kolmogorov_complexity dbr:Probability dbr:Recursively_enumerable dbr:Statistical_randomness dbr:Gregory_Chaitin dbr:Halting_problem dbc:Randomness dbr:Independence_(probability_theory) dbr:Cantor_space dbr:Chaitin's_constant dbr:Sequence dbr:Martingale_(probability_theory) dbr:Universal_Turing_machine dbr:Turing_reduction dbr:Random_sequence dbr:Randomness_test dbr:Turing_degree dbr:Turing_reducible dbr:Betting dbr:Claus-Peter_Schnorr dbr:Computable dbr:Péter_Gács |
| dbp:date | June 2021 (en) |
| dbp:reason | Similar in what way? In that both theorems concern Turing machines and/or computability? (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Explain dbt:More_footnotes dbt:Reflist dbt:Su dbt:Distinguish-redirect |
| dcterms:subject | dbc:Algorithmic_information_theory dbc:Randomness |
| gold:hypernym | dbr:Sequence |
| rdf:type | owl:Thing |
| rdfs:comment | アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、英: Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。 (ja) 알고리즘 무작위 수열(Algorithmic random sequence)이란 어떤 알고리즘에 대해서 각 알파벳이 무작위하게 등장한다고 간주되는 무한수열이다. 무작위 수열을 정의하는데 쓰이는 알고리즘의 종류는 매우 다양하기 때문에 무작위성에도 서로 다른 정의가 있다. 마틴-뢰프 무작위성(Martin-Löf randomnes)은 그 중 가장 흔하게 사용되는 정의이다. 무작위 수열은 의 주요한 연구주제중 하나이다. (ko) Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. The class of all Martin-Löf random (binary) sequences is denoted by RAND or MLR. (en) Intuitivamente, una secuencia algorítmicamente aleatoria (o secuencia aleatoria) es una secuencia infinita de dígitos binarios que aparece aleatoria a cualquier algoritmo. La definición no puede aplicarse igualmente bien a las secuencias en cualquier conjunto finito de caracteres, pero ingenuamente aplica en la práctica. Las secuencias aleatorias son los objetos principales de estudio en la teoría algorítmica de la información. La clase de aleatoria de secuencias de Martin-Löf (binario) se denota por RAND o MLR. (es) Intuitivamente, uma sequência algoritmicamente aleatória (ou 'sequência aleatória' ) é uma sequência infinita de dígitos binários que parece aleatória para qualquer algoritmo. O conceito pode ser aplicado analogamente para as sequências em qualquer alfabeto finito (por exemplo, dígitos decimais). Sequências aleatórias são objetos-chave de estudo em teoria algorítmica da informação. A classe de todas as sequências aleatórias Martin-Löf (binária) é denotada por RAND ou MLR. (pt) |
| rdfs:label | Algorithmically random sequence (en) Secuencia algorítmicamente aleatoria (es) アルゴリズム的ランダムな無限列 (ja) 알고리즘 난수열 (ko) Sequência algoritmicamente aleatória (pt) |
| owl:differentFrom | dbr:Randomized_algorithms |
| owl:sameAs | freebase:Algorithmically random sequence wikidata:Algorithmically random sequence wikidata:Algorithmically random sequence dbpedia-es:Algorithmically random sequence dbpedia-ja:Algorithmically random sequence dbpedia-ko:Algorithmically random sequence dbpedia-pt:Algorithmically random sequence https://global.dbpedia.org/id/4o7hB |
| prov:wasDerivedFrom | wikipedia-en:Algorithmically_random_sequence?oldid=1108975092&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Algorithmically_random_sequence |
| is dbo:knownFor of | dbr:Per_Martin-Löf |
| is dbo:wikiPageRedirects of | dbr:Algorithmically_random_set dbr:Martin-Loef_random dbr:Martin-Lof_random dbr:Martin-Löf_random dbr:Martin-Löf_randomness dbr:1-random_real dbr:1-randomness dbr:Algorithmic_randomness dbr:Algorithmically_random |
| is dbo:wikiPageWikiLink of | dbr:Algorithmic_information_theory dbr:John_von_Neumann dbr:Per_Martin-Löf dbr:Reverse_mathematics dbr:Universality_probability dbr:Definable_real_number dbr:Index_of_cryptography_articles dbr:Claus_P._Schnorr dbr:Pseudorandom_noise dbr:K-trivial_set dbr:Normal_number dbr:Kolmogorov_complexity dbr:Random_number dbr:Effective_dimension dbr:Algorithmically_random_set dbr:Real_number dbr:Chaitin's_constant dbr:Outline_of_computer_programming dbr:Martin-Loef_random dbr:Martin-Lof_random dbr:Randomness_test dbr:Yongge_Wang dbr:Martin-Löf_random dbr:Martin-Löf_randomness dbr:1-random_real dbr:1-randomness dbr:Algorithmic_randomness dbr:Algorithmically_random |
| is dbp:knownFor of | dbr:Per_Martin-Löf |
| is foaf:primaryTopic of | wikipedia-en:Algorithmically_random_sequence |