×

The complexity of uniform distribution. (English) Zbl 0820.03031

Summary: We investigate the notion of testable sequence which was proposed by R. Winkler [ibid. 43, No. 4, 493-512 (1993; Zbl 0813.65001)], and we show that the set of uniformly distributed sequences is \(\Pi^ 0_ 3\)- complete, hence not refutable.

MSC:

03D80 Applications of computability and recursion theory
11B50 Sequences (mod \(m\))
11K45 Pseudo-random numbers; Monte Carlo methods
03D20 Recursive functions and relations, subrecursive hierarchies
03E15 Descriptive set theory
03D55 Hierarchies of computability and definability

Citations:

Zbl 0813.65001
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] MOSCHOVAKIS Y. N.: Descriptive Set Theory. Stud. Logic Found. Math. 100, North-Holland, Amsterdam-New York-Oxford, 1980. · Zbl 0433.03025
[2] ROGERS H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, London, 1967. · Zbl 0183.01401
[3] WINKLER R.: Some remarks on pseudorandom sequences. Math. Slovaca 43 (1993), 493-512. · Zbl 0813.65001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.