Characterising the Martin-Löf random sequences using computably enumerable sets of measure one

dc.contributor.author	Davie G.	en
dc.date.accessioned	2012-11-01T16:31:36Z
dc.date.available	2012-11-01T16:31:36Z
dc.date.issued	2004	en
dc.identifier.citation	Information Processing Letters	en
dc.identifier.citation	92	en
dc.identifier.citation	3	en
dc.identifier.issn	200190	en
dc.identifier.other	10.1016/j.ipl.2004.06.016	en
dc.identifier.uri	http://hdl.handle.net/10500/7423
dc.description.abstract	The Martin-Löf random sequences using the computably enumerable (c.e.) sets of measure one was characterized. It was found that an infinite binary sequence is Martin-Löf random, if it passes all Martin-Löf tests. It was shown that a set of binary strings of ever decreasing nature can be encoded of any c.e. set of measure one as a Martin-Löf test. Martin-Löf proved that an infinite binary sequences passes all these tests with probability one.	en
dc.language.iso	en	en
dc.subject	Compressibility coefficient; Computational complexity; Kolmogorov complexity; Martin-Löf random; Probability law Algorithms; Computational complexity; Data processing; Mathematical operators; Probability; Random processes; Set theory; Theorem proving; Compressability coefficients; Kolmogorov complexity; Martin-Löf random; Probability law; Binary sequences	en
dc.title	Characterising the Martin-Löf random sequences using computably enumerable sets of measure one	en
dc.type	Article	en