Computational depth and reducibility. (English) Zbl 0821.68052
Summary: This paper reviews and investigates Bennet’s notions of strong and weak computational depth (also called logical depth) for infinite binary sequences. Roughly, an infinite binary sequence \(x\) is defined to be weakly useful if every element of nonnegligible set of decidable sequences is reducible to \(x\) in recursively bounded time. It is shown that every weakly useful sequence is strongly deep. This result (which generalizes Bennet’s observation that the halting problem is strongly deep) implies that every high Turing degree contains strongly deep sequences. It is also shown that, in the sense of Baire category, almost every infinite binary sequence is weakly deep, but not strongly deep.
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 03D10 | Turing machines and related notions |
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
References:
| [1] | Adleman, L., Time, space, and randomness, (Technical Report MIT/LCS/79/TM-131 (1979), Massachusettes Institute of Technology, Laboratory for Computer Science) |
| [2] | Balcázar, J. L.; Diaz, J.; Gabarró, J., Structural Complexity I (1988), Springer: Springer Berlin · Zbl 0638.68040 |
| [3] | Barzdin’, Y. M., Complexity of programs to determine whether natural numbers not greater than \(n\) belong to a recursively enumerable set, Soviet Math. Dokl., 9, 1251-1254 (1968) · Zbl 0193.31601 |
| [4] | Bennett, C. H.; Pines, D., Dissipation, information, computational complexity and the definition of organization, Emerging Syntheses in Science, Proceedings of the Founding Workshops of the Santa Fe Institute, 297-313 (1985) |
| [5] | Bennett, C. H., Logical depth and physical complexity, (Herken, R., The Universal Turing Machine: A Half-Century Survey (1988), Oxford University Press: Oxford University Press Oxford), 227-257 · Zbl 0668.03017 |
| [6] | Billingsley, P., Probability and Measure (1986), Wiley: Wiley New York · Zbl 0649.60001 |
| [7] | R.V. Book, On languages reducible to algorithmically random languages, SIAM. J. Comput; R.V. Book, On languages reducible to algorithmically random languages, SIAM. J. Comput · Zbl 0834.68027 |
| [8] | R.V. Book, J.H. Lutz and K.W. Wagner, An observation on probability versus randomness with applications to complexity classes. Math. Systems Theory; R.V. Book, J.H. Lutz and K.W. Wagner, An observation on probability versus randomness with applications to complexity classes. Math. Systems Theory · Zbl 0819.68056 |
| [9] | Chaitin, G. J., On the length of programs for computing finite binary sequences, J. Assoc. Comput. Mach., 13, 547-569 (1966) · Zbl 0158.25301 |
| [10] | Chaitin, G. J., On the length of programs for computing finite binary sequences: statistical considerations, J. Assoc. Comput. Mach., 16, 145-159 (1969) · Zbl 0187.28303 |
| [11] | Chaitin, G. J., A theory of program size formally identical to information theory, J. Assoc. Comput. Mach., 22, 329-340 (1975) · Zbl 0309.68045 |
| [12] | Chaitin, G. J., Incompleteness theorems for random reals, Adv. in Appl. Math., 8, 119-146 (1987) · Zbl 0649.03046 |
| [13] | Cover, T. M.; Thomas, J. A., Elements of Information Theory (1991), Wiley: Wiley New York · Zbl 0762.94001 |
| [14] | Freidzon, R. I., Families of recursive predicates of measure zero, J. Soviet Math., 6, 449-455 (1976), translated in · Zbl 0375.02032 |
| [15] | Gács, P., On the symmetry of algorithmic information, Soviet Math. Dokl., 15, 1477 (1974) · Zbl 0314.94019 |
| [16] | Gács, P., Every sequence is reducible to a random one, Inform. and Control, 70, 186-192 (1986) · Zbl 0628.03024 |
| [17] | Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 675-695 (1977) · Zbl 0366.02024 |
| [18] | Halmos, P. R., Measure Theory (1950), Springer: Springer Berlin · Zbl 0117.10502 |
| [19] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 |
| [20] | Kelley, J. L., General Topology (1955), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0066.16604 |
| [21] | Kolmogorov, A. N., Three approaches to the quantitative definition of ‘information’, Problems of Information Transmission, 1, 1-7 (1965) · Zbl 0271.94018 |
| [22] | Kolmogorov, A. N., Logical basis for information theory and probability theory, IEEE Trans. Inform. Theory, IT-14, 662-664 (1968) · Zbl 0167.47601 |
| [23] | Kolmogorov, A. N.; Uspenskii, V. A., Algorithms and randomness, Theory Probab. Appl., 32, 389-412 (1987), translated in · Zbl 0648.60005 |
| [24] | Koppel, M., Complexity, depth, and sophistication, Complex Systems, 1, 1087-1091 (1987) · Zbl 0656.68049 |
| [25] | Koppel, M., Structure, (Herken, R., The Universal Turing Machine: A Half-Century Survey (1988), Oxford University Press: Oxford University Press Oxford), 435-452 · Zbl 0665.68031 |
| [26] | Levin, L. A., On the notion of a random sequence, Soviet Math. Dokl., 14, 1413-1416 (1973) · Zbl 0312.94006 |
| [27] | Levin, L. A., Laws of information conservation (nongrowth) and aspects of the foundation of probability theory, Problems of Information Transmission, 10, 206-210 (1974) |
| [28] | Levin, L. A., On the principle of conservation of information in intuitionistic mathematics, Soviet Math. Dokl., 17, 601-605 (1976) · Zbl 0358.02033 |
| [29] | Levin, L. A., Uniform tests of randomness, Soviet Math. Dokl., 17, 337-340 (1976) · Zbl 0341.94013 |
| [30] | Levin, L. A., Various measures of complexity for finite objects (axiomatic description), Soviet Math. Dokl., 17, 522-526 (1976) · Zbl 0347.68035 |
| [31] | Levin, L. A., Randomness conservation inequalities; information and independence in mathematical theories, Inform. and Control, 61, 15-37 (1984) · Zbl 0592.03035 |
| [32] | Levin, L. A.; V’jugin, V. V., Invariant properties of informational bulks, Proceedings of the Sixth Symposium on Mathematical Foundations of Computer Science, 359-364 (1977) · Zbl 0409.94019 |
| [33] | Li, M.; Vitányi, P. M.B., Kolmogorov complexity and its applications, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A (1990), Elsevier: Elsevier Amsterdam), 187-254 · Zbl 0900.68264 |
| [34] | Li, M.; Vitányi, P. M.B., Learning simple concepts under simple distributions, SIAM J. Comput., 20, 911-935 (1991) · Zbl 0751.68055 |
| [35] | Li, M.; Vitányi, P. M.B., An Introduction to Kolmogorov Complexity and its Applications (1993), Springer: Springer Berlin · Zbl 0805.68063 |
| [36] | J.H. Lutz, Resource-bounded measure, in preparation.; J.H. Lutz, Resource-bounded measure, in preparation. |
| [37] | Lutz, J. H., Almost everywhere high nonuniform complexity, J. Comput. System Sci., 44, 220-258 (1992) · Zbl 0767.68043 |
| [38] | Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlag. Math., 12, 295-310 (1966) · Zbl 0181.30504 |
| [39] | Martin-Löf, P., On the definition of random sequences, Inform. and Control, 9, 602-619 (1966) · Zbl 0244.62008 |
| [40] | Martin-Löf, P., Complexity oscillations in infinite binary sequences, Seitschrift für Wahrscheinlichkeits-theory and Verwandte Gebiete, 19, 225-230 (1971) · Zbl 0212.23103 |
| [41] | Mehlhorn, K., The “almost all” theory of subrecursive degrees is decidable, (Proceedings of the Second Colloquium on Automata, Languages and Programming. Proceedings of the Second Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 14 (1974), Springer: Springer Berlin), 317-325 · Zbl 0284.68041 |
| [42] | Moschovakis, Y. N., Descriptive Set Theory (1980), North-Holland: North-Holland Amsterdam · Zbl 0433.03025 |
| [43] | Oxtoby, J. C., Measure and Category (1980), Springer Berlin · Zbl 0217.09201 |
| [44] | Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401 |
| [45] | Royden, H. L., Real Analysis (1988), Macmillan: Macmillan New York · Zbl 0704.26006 |
| [46] | Sacks, G. E., Degrees of Unsolvability (1966), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0118.25202 |
| [47] | Schnorr, C. P., Process complexity and effective random tests, J. Comput. System Sci., 7, 376-388 (1973) · Zbl 0273.68036 |
| [48] | Shen’, A. Kh., The frequency approach to defining a random sequence, Semiotika i Informatika, 19, 14-42 (1982), (In Russian) |
| [49] | Shen’, A. Kh., On relations between different algorithmic definitions of randomness, Soviet Math. Dokl., 38, 316-319 (1989) · Zbl 0683.60002 |
| [50] | Soare, R. I., Recursively Enumerable Sets and Degrees (1987), Springer: Springer Berlin · Zbl 0667.03030 |
| [51] | Solomonoff, R. J., A formal theory of inductive inference, Inform. and Control. Inform. and Control, Inform. and Control, 7, 224-254 (1964) · Zbl 0259.68038 |
| [52] | R.M. Solovay, 1975, reported in [12].; R.M. Solovay, 1975, reported in [12]. |
| [53] | V’jugin, V. V., On Turing invariant sets, Soviet Math. Dokl., 17, 1090-1094 (1976) · Zbl 0359.02041 |
| [54] | V’jugin, V. V., The algebra of invariant properties of finite sequences, Problems of Inform. Transmission, 18, 147-161 (1982) · Zbl 0525.03035 |
| [55] | Zvonkin, A. K.; Levin, L. A., The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Math. Surveys, 25, 83-124 (1970) · Zbl 0222.02027 |
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.
