Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-01-09T12:35:40.231Z Has data issue: false hasContentIssue false
  • English
  • Français

General random sequences and learnable sequences

Published online by Cambridge University Press:  12 March 2014

C. P. Schnorr  and
P. Fuchs
C. P. Schnorr
Affiliation:
Universität Frankfurt, Fachbereich Mathematik, Federal Republic of Germany
P. Fuchs
Affiliation:
Universität Frankfurt, Fachbereich Mathematik, Federal Republic of Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequence z is learnable (super-learnable, resp.) if and only if there is a computable probability measure p such that p is Schnorr (Martin-Löf, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 42 , Issue 3 , September 1977 , pp. 329 - 340
Copyright
Copyright © Association for Symbolic Logic 1977

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Blum, M., A machine-independent theory of the complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14, (1967), pp. 322–336.CrossRefGoogle Scholar
[2]Daley, R. P., On the learning of non-recursive sequences, Proceedings of the Princeton Conference on Information Sciences and Systems, 1973.Google Scholar
[3]Fuchs, P. H., Programmkomplexität, Zufälligkeit, Lembarkeit, Dissertation, Universität Frankfurt, 1975.Google Scholar
[4]Levin, L. A., On the notion of a random sequence, Soviet Mathematics, Doklady, vol. 14 (1973), pp. 1413–1416.Google Scholar
[5]Kolmogorov, A. N., Three approaches to the definition of the concept of the “amount of information”, Problemy Peredači Informacii, vol. 1 (1965), pp. 3–11.Google Scholar
[6]Martin-Löf, P., The definition of random sequences, Information and Control, vol. 8 (1966), pp. 602–619.CrossRefGoogle Scholar
[7]Schnorr, C. P., Zufälligkeit und Wahrscheinlichkeit, eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, Berlin and New York, 1971.Google Scholar
[8]Schnorr, C. P., Process complexity and effective random tests, Journal of Computer and System Sciences, vol. 7 (1973), pp. 376–388.CrossRefGoogle Scholar
[9]Schnorr, C. P., A unified approach to the definition of random sequences, Mathematical System Theory, vol. 5 (1971), pp. 246–258.CrossRefGoogle Scholar
[10]Schnorr, C. P., Eine Bemerkung zum Begriff der zufälligen Folge, Zettsckrift für Wahrscheinlich-keitstheorie und Verwandte Gebiete, vol. 14 (1969), pp. 27–35.CrossRefGoogle Scholar
[11]Schnorr, C. P., A surview on the theory of random sequences, Logic, methodology and philosophy of science (Butts, R., Hintikka, J., Editors), Reidel, Dordrecht, 1977.Google Scholar
[12]Blum, M., On effective procedures for speeding up algorithms, Journal of the Association for Computing Machinery, vol. 18 (1971), pp. 290–305.CrossRefGoogle Scholar
[13]Gacs, P., personal communication.Google Scholar