文章基本信息

标题：Invariance Properties of Random Sequences
本地全文：下载
作者：Peter Hertling ; Yongge Wang
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：1997
卷号：3
期号：11
页码：1241-1249
出版社：Graz University of Technology and Know-Center
摘要：We present invariance characterizations of different types of random sequences. We correct Schnorr's original, incorrect characterization of Martin-Loef ran dom sequences, compare it with Schnorr s corresponding characterization of his own randomness concept, and give a similar, new characterization of Kurtz random sequences. That is, we show that an infinite sequence is Kurtz random if and only if for every partial, computable, measure-invariant function the sequence is not recursive. 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.