Aggarwal, Gagan; Goldwasser, Michael H.; Kao, Ming-Yang; Schweller, Robert T. Complexities for generalized models of self-assembly. (English) Zbl 1318.68088 Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 880-889 (2004). MSC: 68Q17 68Q05 68Q10 68Q25 68Q30 PDFBibTeX XMLCite \textit{G. Aggarwal} et al., in: Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11--13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 880--889 (2004; Zbl 1318.68088)
Davie, George Characterising the Martin-Löf random sequences using computably enumerable sets of measure one. (English) Zbl 1173.68540 Inf. Process. Lett. 92, No. 3, 157-160 (2004). MSC: 68Q30 68Q17 60A99 PDFBibTeX XMLCite \textit{G. Davie}, Inf. Process. Lett. 92, No. 3, 157--160 (2004; Zbl 1173.68540) Full Text: DOI
Durand, Bruno; Vereshchagin, Nikolai Kolmogorov-Loveland stochasticity for finite strings. (English) Zbl 1177.60008 Inf. Process. Lett. 91, No. 6, 263-269 (2004). MSC: 60A99 68Q30 PDFBibTeX XMLCite \textit{B. Durand} and \textit{N. Vereshchagin}, Inf. Process. Lett. 91, No. 6, 263--269 (2004; Zbl 1177.60008) Full Text: DOI
Poland, Jan A coding theorem for enumerable output machines. (English) Zbl 1178.68247 Inf. Process. Lett. 91, No. 4, 157-161 (2004). MSC: 68P30 PDFBibTeX XMLCite \textit{J. Poland}, Inf. Process. Lett. 91, No. 4, 157--161 (2004; Zbl 1178.68247) Full Text: DOI
Takahashi, Hayato Redundancy of universal coding, Kolmogorov complexity, and Hausdorff dimension. (English) Zbl 1298.94059 IEEE Trans. Inf. Theory 50, No. 11, 2727-2736 (2004). MSC: 94A29 28A80 60C05 68Q30 PDFBibTeX XMLCite \textit{H. Takahashi}, IEEE Trans. Inf. Theory 50, No. 11, 2727--2736 (2004; Zbl 1298.94059) Full Text: DOI
Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitányi, Paul M. B. The similarity metric. (English) Zbl 1316.68052 IEEE Trans. Inf. Theory 50, No. 12, 3250-3264 (2004). MSC: 68P30 05A05 68Q30 92D20 PDFBibTeX XMLCite \textit{M. Li} et al., IEEE Trans. Inf. Theory 50, No. 12, 3250--3264 (2004; Zbl 1316.68052) Full Text: DOI
Chen, Xin; Francia, Brent; Li, Ming; McKinnon, Brian; Seker, Amit Shared information and program plagiarism detection. (English) Zbl 1294.94010 IEEE Trans. Inf. Theory 50, No. 7, 1545-1551 (2004). MSC: 94A15 68Q30 PDFBibTeX XMLCite \textit{X. Chen} et al., IEEE Trans. Inf. Theory 50, No. 7, 1545--1551 (2004; Zbl 1294.94010) Full Text: DOI
Athreya, Krishna B.; Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira Effective strong dimension in algorithmic information and computational complexity. (English) Zbl 1122.68068 Diekert, Volker (ed.) et al., STACS 2004. 21st annual symposium on theoretical aspects of computer science, Montpellier, France, March 25–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21236-1/pbk). Lecture Notes in Computer Science 2996, 632-643 (2004). MSC: 68Q30 68Q15 28A80 03D45 PDFBibTeX XMLCite \textit{K. B. Athreya} et al., Lect. Notes Comput. Sci. 2996, 632--643 (2004; Zbl 1122.68068) Full Text: DOI
Allender, Eric; Buhrman, Harry; Koucký, Michal What can be efficiently reduced to the K-random strings? (English) Zbl 1122.68445 Diekert, Volker (ed.) et al., STACS 2004. 21st annual symposium on theoretical aspects of computer science, Montpellier, France, March 25–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21236-1/pbk). Lecture Notes in Computer Science 2996, 584-595 (2004). MSC: 68Q15 68Q30 PDFBibTeX XMLCite \textit{E. Allender} et al., Lect. Notes Comput. Sci. 2996, 584--595 (2004; Zbl 1122.68445) Full Text: DOI
Brito, Carlos; Gafni, Eli; Vaya, Shailesh An information theoretic lower bound for broadcasting in radio networks. (English) Zbl 1122.90320 Diekert, Volker (ed.) et al., STACS 2004. 21st annual symposium on theoretical aspects of computer science, Montpellier, France, March 25–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21236-1/pbk). Lecture Notes in Computer Science 2996, 534-546 (2004). MSC: 90B18 68M12 68Q30 94A15 PDFBibTeX XMLCite \textit{C. Brito} et al., Lect. Notes Comput. Sci. 2996, 534--546 (2004; Zbl 1122.90320) Full Text: DOI
Chernov, A. V. Complexity of sets obtained as values of propositional formulas. (English. Russian original) Zbl 1114.03004 Math. Notes 75, No. 1, 131-139 (2004); translation from Mat. Zametki 75, No. 1, 142-150 (2004). MSC: 03B05 68Q30 PDFBibTeX XMLCite \textit{A. V. Chernov}, Math. Notes 75, No. 1, 131--139 (2004; Zbl 1114.03004); translation from Mat. Zametki 75, No. 1, 142--150 (2004) Full Text: DOI
Terwijn, S. A. Complexity and randomness. (English) Zbl 1121.68058 Rend. Semin. Mat., Torino 62, No. 1, 1-37 (2004). Reviewer: Frank Stephan (Singapore) MSC: 68Q30 68-02 03D15 03D28 03D80 28E15 PDFBibTeX XMLCite \textit{S. A. Terwijn}, Rend. Semin. Mat., Torino 62, No. 1, 1--37 (2004; Zbl 1121.68058)
Ushakov, M. A. Kolmogorov complexity of the initial segments of almost periodic sequences. (Russian, English) Zbl 1084.68056 Vestn. Mosk. Univ., Ser. I 2004, No. 4, 3-6 (2004); translation in Mosc. Univ. Math. Bull. 59, No. 4, 1-4 (2004). Reviewer: V. G. Miladzhanov (Andizhan) MSC: 68Q30 37B10 PDFBibTeX XMLCite \textit{M. A. Ushakov}, Vestn. Mosk. Univ., Ser. I 2004, No. 4, 3--6 (2004; Zbl 1084.68056); translation in Mosc. Univ. Math. Bull. 59, No. 4, 1--4 (2004)
Reimann, Jan Computability and fractal dimension. (English) Zbl 1080.03031 Heidelberg: Universität Heidelberg, Naturwissenschaftlich-Mathematische Gesamtfakultät (Dissertation). xi, 126 p. (2004). Reviewer: Vesa Halava (Turku) MSC: 03D45 28A80 68Q30 03D25 PDFBibTeX XMLCite \textit{J. Reimann}, Computability and fractal dimension. Heidelberg: Universität Heidelberg, Naturwissenschaftlich-Mathematische Gesamtfakultät (Dissertation) (2004; Zbl 1080.03031) Full Text: Link
Dai, Jack Jie A computable version of the random signs problem and Kolmogorov complexity. (English) Zbl 1130.68065 Stat. Probab. Lett. 67, No. 1, 27-31 (2004). MSC: 68Q30 60C05 PDFBibTeX XMLCite \textit{J. J. Dai}, Stat. Probab. Lett. 67, No. 1, 27--31 (2004; Zbl 1130.68065) Full Text: DOI
Yu, Liang; Ding, Decheng There in no sw-complete c.e. real. (English) Zbl 1070.03028 J. Symb. Log. 69, No. 4, 1163-1170 (2004). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 03D80 68Q30 PDFBibTeX XMLCite \textit{L. Yu} and \textit{D. Ding}, J. Symb. Log. 69, No. 4, 1163--1170 (2004; Zbl 1070.03028) Full Text: DOI
Miller, Joseph S. Every 2-random real is Kolmogorov random. (English) Zbl 1090.03012 J. Symb. Log. 69, No. 3, 907-913 (2004). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 03D80 68Q30 PDFBibTeX XMLCite \textit{J. S. Miller}, J. Symb. Log. 69, No. 3, 907--913 (2004; Zbl 1090.03012) Full Text: DOI
Merkle, Wolfgang; Mihailović, Nenad On the construction of effectively random sets. (English) Zbl 1090.03011 J. Symb. Log. 69, No. 3, 862-878 (2004). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 03D80 68Q30 60G42 03D25 PDFBibTeX XMLCite \textit{W. Merkle} and \textit{N. Mihailović}, J. Symb. Log. 69, No. 3, 862--878 (2004; Zbl 1090.03011) Full Text: DOI
Downey, Rodney G.; Griffiths, Evan J. Schnorr randomness. (English) Zbl 1072.03025 J. Symb. Log. 69, No. 2, 533-554 (2004). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 03D80 03F60 68Q30 PDFBibTeX XMLCite \textit{R. G. Downey} and \textit{E. J. Griffiths}, J. Symb. Log. 69, No. 2, 533--554 (2004; Zbl 1072.03025) Full Text: DOI
Merkle, Wolfgang; Mihailović, Nenad; Slaman, Theodore A. Some results on effective randomness. (English) Zbl 1099.03033 Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 983-995 (2004). MSC: 03D80 68Q30 60G42 03D45 PDFBibTeX XMLCite \textit{W. Merkle} et al., Lect. Notes Comput. Sci. 3142, 983--995 (2004; Zbl 1099.03033) Full Text: DOI
Martin, Keye Entropy as a fixed point. (English) Zbl 1099.68644 Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 945-958 (2004). MSC: 68Q30 68Q17 94A17 PDFBibTeX XMLCite \textit{K. Martin}, Lect. Notes Comput. Sci. 3142, 945--958 (2004; Zbl 1099.68644) Full Text: DOI
Hitchcock, John M.; López-Valdés, María; Mayordomo, Elvira Scaled dimension and the Kolmogorov complexity of Turing-hard sets. (English) Zbl 1096.68073 Fiala, Jiří(ed.) et al., Mathematical foundations of computer Science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22823-3/pbk). Lecture Notes in Computer Science 3153, 476-487 (2004). MSC: 68Q30 68Q15 PDFBibTeX XMLCite \textit{J. M. Hitchcock} et al., Lect. Notes Comput. Sci. 3153, 476--487 (2004; Zbl 1096.68073) Full Text: DOI
Lee, Troy; Romashchenko, Andrei On polynomially time bounded symmetry of information. (English) Zbl 1096.68074 Fiala, Jiří(ed.) et al., Mathematical foundations of computer Science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22823-3/pbk). Lecture Notes in Computer Science 3153, 463-475 (2004). MSC: 68Q30 68Q15 PDFBibTeX XMLCite \textit{T. Lee} and \textit{A. Romashchenko}, Lect. Notes Comput. Sci. 3153, 463--475 (2004; Zbl 1096.68074) Full Text: DOI
Downey, Rod Some recent progress in algorithmic randomness. (English) Zbl 1096.03055 Fiala, Jiří(ed.) et al., Mathematical foundations of computer Science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22823-3/pbk). Lecture Notes in Computer Science 3153, 42-83 (2004). MSC: 03D80 68Q30 03-02 68-02 PDFBibTeX XMLCite \textit{R. Downey}, Lect. Notes Comput. Sci. 3153, 42--83 (2004; Zbl 1096.03055) Full Text: DOI
Fortnow, Lance Kolmogorov complexity and computational complexity. (English) Zbl 1083.68052 Krajíček, Jan (ed.), Complexity of computations and proofs. Rome: Aracne; Napoli: Dipartimento di Matematica della Seconda Università di Napoli (ISBN 88-7999-413-1/hbk). Quaderni di Matematica 13, 229-248 (2004). Reviewer: Christoph Meinel (Trier) MSC: 68Q30 68Q15 PDFBibTeX XMLCite \textit{L. Fortnow}, Quad. Mat. 13, 229--248 (2004; Zbl 1083.68052)
Maslov, Victor; V’yugin, Vladimir Maximum entropy principle in non-ordered setting. (English) Zbl 1110.68401 Ben-David, Shai (ed.) et al., Algorithmic learning theory. 15th international conference, ALT 2004, Padova, Italy, October 2–5, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23356-3/pbk). Lecture Notes in Computer Science 3244. Lecture Notes in Artificial Intelligence, 221-233 (2004). MSC: 68Q32 68Q30 PDFBibTeX XMLCite \textit{V. Maslov} and \textit{V. V'yugin}, Lect. Notes Comput. Sci. 3244, 221--233 (2004; Zbl 1110.68401) Full Text: DOI
Kreinovich, V.; Finkelstein, A. M. Towards applying computational complexity to foundations of physics. (English) Zbl 1072.81005 Zap. Nauchn. Semin. POMI 316, 63-110 (2004); translation in J. Math. Sci., New York 134, No. 5, 2358-2382 (2006). Reviewer: Nicolae Constantinescu (Craiova) MSC: 81P05 00A30 68Q99 68Q30 03A05 81Q99 PDFBibTeX XMLCite \textit{V. Kreinovich} and \textit{A. M. Finkelstein}, Zap. Nauchn. Semin. POMI 316, 63--110 (2004; Zbl 1072.81005); translation in J. Math. Sci., New York 134, No. 5, 2358--2382 (2006) Full Text: EuDML
Zheng, Xizhong; Rettinger, Robert On the extensions of Solovay-reducibility. (English) Zbl 1091.03013 Chwa, Kyung-Yong (ed.) et al., Computing and combinatorics. 10th annual international conference, COCOON 2004, Jeju Island, Korea, August 17–20, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22856-X/pbk). Lecture Notes in Computer Science 3106, 360-369 (2004). MSC: 03D30 68Q30 PDFBibTeX XMLCite \textit{X. Zheng} and \textit{R. Rettinger}, Lect. Notes Comput. Sci. 3106, 360--369 (2004; Zbl 1091.03013) Full Text: DOI
Hromkovič, Juraj Theoretical informatics. Computability, complexity theory, algorithmics, cryptography. An introduction. 2nd, revised and extended ed. (Theoretische Informatik. Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung.) (German) Zbl 1069.68046 Leitfäden der Informatik. Stuttgart: Teubner (ISBN 3-519-10332-X/pbk). 335 p. (2004). MSC: 68Q01 68Q05 68Q15 68-01 68Q25 68Q30 68W20 94A60 94A62 PDFBibTeX XMLCite \textit{J. Hromkovič}, Theoretische Informatik. Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung. 2nd, revised and extended ed. Stuttgart: Teubner (2004; Zbl 1069.68046)
Bar-Yam, Y. Multiscale complexity/entropy. (English) Zbl 1098.94010 Adv. Complex Syst. 7, No. 1, 47-63 (2004). MSC: 94A17 68P30 68Q30 PDFBibTeX XMLCite \textit{Y. Bar-Yam}, Adv. Complex Syst. 7, No. 1, 47--63 (2004; Zbl 1098.94010) Full Text: DOI
Ferbus-Zanda, Marie; Grigorieff, Serge Is randomness “native” to computer science? (English) Zbl 1063.68592 Păun, G. (ed.) et al., Current trends in theoretical computer science. The challenge of the new century. Vol. 2: Formal models and semantics. River Edge, NJ: World Scientific (ISBN 981-238-965-2/hbk; 981-238-783-8/set). 141-179 (2004). MSC: 68Q30 PDFBibTeX XMLCite \textit{M. Ferbus-Zanda} and \textit{S. Grigorieff}, in: Current trends in theoretical computer science. The challenge of the new century. Vol. 2: Formal models and semantics. River Edge, NJ: World Scientific. 141--179 (2004; Zbl 1063.68592)
Lee, Cassey Emergence and universal computation. (English) Zbl 1092.68039 Metroeconomica 55, No. 2-3, 219-238 (2004). MSC: 68Q05 68Q30 68Q80 91B06 91B24 PDFBibTeX XMLCite \textit{C. Lee}, Metroeconomica 55, No. 2--3, 219--238 (2004; Zbl 1092.68039) Full Text: DOI
McCall, John J. Induction: from Kolmogorov and Solomonoff to de Finetti and back to Kolmogorov. (English) Zbl 1089.60006 Metroeconomica 55, No. 2-3, 195-218 (2004). MSC: 60-03 68Q30 60A05 01A60 PDFBibTeX XMLCite \textit{J. J. McCall}, Metroeconomica 55, No. 2--3, 195--218 (2004; Zbl 1089.60006) Full Text: DOI
Carette, Jacques Understanding expression simplification. (English) Zbl 1134.68596 Gutierrez, Jaime (ed.), ISSAC 2004. Proceedings of the 2004 international symposium on symbolic and algebraic computation, Santander, Spain, July 4–7, 2004. New York, NY: ACM Press (ISBN 1-58113-827-X/pbk). 72-79 (2004). MSC: 68W30 68Q30 PDFBibTeX XMLCite \textit{J. Carette}, in: Proceedings of the 2004 international symposium on symbolic and algebraic computation, ISSAC 2004, Santander, Spain, July 4--7, 2004. New York, NY: ACM Press. 72--79 (2004; Zbl 1134.68596)
Artstein, S.; Milman, V.; Szarek, S.; Tomczak-Jaegermann, N. On convexified packing and entropy duality. (English) Zbl 1062.52023 Geom. Funct. Anal. 14, No. 5, 1134-1141 (2004). Reviewer: S. S. Kutateladze (Novosibirsk) MSC: 52C45 46B20 47B06 46B10 PDFBibTeX XMLCite \textit{S. Artstein} et al., Geom. Funct. Anal. 14, No. 5, 1134--1141 (2004; Zbl 1062.52023) Full Text: DOI arXiv
Savari, Serap A. Compressing a representation of events in a concurrent system. (English) Zbl 1064.94537 Gupta, Piyush (ed.) et al., Advances in Network information theory. DIMACS workshop network information theory, March 17–19, 2003, Piscataway, New Jersey, USA. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3467-3/hbk). DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 66, 25-42 (2004). MSC: 94A34 94A17 68P30 94A29 68Q30 PDFBibTeX XMLCite \textit{S. A. Savari}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 66, 25--42 (2004; Zbl 1064.94537)
Downey, Rod; Griffiths, Evan; Laforte, Geoffrey On Schnorr and computable randomness, martingales, and machines. (English) Zbl 1062.68064 Math. Log. Q. 50, No. 6, 613-627 (2004). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q30 03D15 03D25 PDFBibTeX XMLCite \textit{R. Downey} et al., Math. Log. Q. 50, No. 6, 613--627 (2004; Zbl 1062.68064) Full Text: DOI
Bojkov, I. V. On the complexity of restoration of functions from the classes \(Q_{r,\gamma}(\Omega,M)\) and \(B_{r,\gamma}(\Omega,M)\) by discrete automata. (Russian. English summary) Zbl 1058.68067 Vychisl. Tekhnol. 9, Spec. Iss. 1, 31-43 (2004). MSC: 68Q45 68Q30 PDFBibTeX XMLCite \textit{I. V. Bojkov}, Vychisl. Tekhnol. 9, 31--43 (2004; Zbl 1058.68067)
Yu, Liang; Ding, Decheng; Downey, Rodney The Kolmogorov complexity of random reals. (English) Zbl 1065.03025 Ann. Pure Appl. Logic 129, No. 1-3, 163-180 (2004). Reviewer: Vladik Ya. Kreinovich (El Paso) MSC: 03D80 68Q30 PDFBibTeX XMLCite \textit{L. Yu} et al., Ann. Pure Appl. Logic 129, No. 1--3, 163--180 (2004; Zbl 1065.03025) Full Text: DOI
Dürr, Christoph; Rapaport, Ivan; Theyssier, Guillaume Cellular automata and communication complexity. (English) Zbl 1068.68087 Theor. Comput. Sci. 322, No. 2, 355-368 (2004). MSC: 68Q80 68Q30 PDFBibTeX XMLCite \textit{C. Dürr} et al., Theor. Comput. Sci. 322, No. 2, 355--368 (2004; Zbl 1068.68087) Full Text: DOI Link
Downey, Rodney G.; Griffiths, Evan J.; Reid, Stephanie On Kurtz randomness. (English) Zbl 1070.68054 Theor. Comput. Sci. 321, No. 2-3, 249-270 (2004). MSC: 68Q30 03D25 03D80 PDFBibTeX XMLCite \textit{R. G. Downey} et al., Theor. Comput. Sci. 321, No. 2--3, 249--270 (2004; Zbl 1070.68054) Full Text: DOI
Hutter, Marcus Optimality of universal Bayesian sequence prediction for general loss and alphabet. (English) Zbl 1094.68037 J. Mach. Learn. Res. 4, No. 6, 971-1000 (2004). MSC: 68Q30 68Q32 68T05 PDFBibTeX XMLCite \textit{M. Hutter}, J. Mach. Learn. Res. 4, No. 6, 971--1000 (2004; Zbl 1094.68037) Full Text: DOI arXiv
Benci, V.; Bonanno, C.; Galatolo, S.; Menconi, G.; Virgilio, M. Dynamical systems and computable information. (English) Zbl 1058.94512 Discrete Contin. Dyn. Syst., Ser. B 4, No. 4, 935-960 (2004). MSC: 94A15 37M25 94A17 37D45 94A08 68P30 68Q30 PDFBibTeX XMLCite \textit{V. Benci} et al., Discrete Contin. Dyn. Syst., Ser. B 4, No. 4, 935--960 (2004; Zbl 1058.94512) Full Text: DOI arXiv
Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira Scaled dimension and nonuniform complexity. (English) Zbl 1084.68055 J. Comput. Syst. Sci. 69, No. 2, 97-122 (2004). MSC: 68Q30 68Q15 28A78 PDFBibTeX XMLCite \textit{J. M. Hitchcock} et al., J. Comput. Syst. Sci. 69, No. 2, 97--122 (2004; Zbl 1084.68055) Full Text: DOI
Downey, Rod G.; Hirschfeldt, Denis R.; LaForte, Geoff Randomness and reducibility. (English) Zbl 1072.03024 J. Comput. Syst. Sci. 68, No. 1, 96-114 (2004). MSC: 03D80 03D30 68Q30 PDFBibTeX XMLCite \textit{R. G. Downey} et al., J. Comput. Syst. Sci. 68, No. 1, 96--114 (2004; Zbl 1072.03024) Full Text: DOI
Allegrini, Paolo; Giuntoli, Martina; Grigolini, Paolo; West, Bruce J. From knowledge, knowability and the search for objective randomness to a new vision of complexity. (English) Zbl 1069.94008 Chaos Solitons Fractals 20, No. 1, 11-32 (2004). MSC: 94A17 68Q30 82C03 PDFBibTeX XMLCite \textit{P. Allegrini} et al., Chaos Solitons Fractals 20, No. 1, 11--32 (2004; Zbl 1069.94008) Full Text: DOI arXiv
Yu, Liang; Ding, Decheng There are \(2^{\aleph_{0}}\) many \(H\)-degrees in the random reals. (English) Zbl 1051.03032 Proc. Am. Math. Soc. 132, No. 8, 2461-2464 (2004). Reviewer: Cristian S. Calude (Auckland) MSC: 03D30 68Q30 PDFBibTeX XMLCite \textit{L. Yu} and \textit{D. Ding}, Proc. Am. Math. Soc. 132, No. 8, 2461--2464 (2004; Zbl 1051.03032) Full Text: DOI
Shagrir, Oron Super-tasks, accelerating Turing machines and uncomputability. (English) Zbl 1072.68042 Theor. Comput. Sci. 317, No. 1-3, 105-114 (2004). MSC: 68Q05 68Q30 PDFBibTeX XMLCite \textit{O. Shagrir}, Theor. Comput. Sci. 317, No. 1--3, 105--114 (2004; Zbl 1072.68042) Full Text: DOI
Burgin, Mark Algorithmic complexity of recursive and inductive algorithms. (English) Zbl 1072.68048 Theor. Comput. Sci. 317, No. 1-3, 31-60 (2004). MSC: 68Q30 68Q05 PDFBibTeX XMLCite \textit{M. Burgin}, Theor. Comput. Sci. 317, No. 1--3, 31--60 (2004; Zbl 1072.68048) Full Text: DOI
Grigorieva, Alla; Grigoriev, Dima Algorithmic aspects of genetic sequences and relative Kolmogorov complexity. (English) Zbl 1100.68578 Int. J. Pure Appl. Math. 11, No. 3, 283-292 (2004). MSC: 68Q30 PDFBibTeX XMLCite \textit{A. Grigorieva} and \textit{D. Grigoriev}, Int. J. Pure Appl. Math. 11, No. 3, 283--292 (2004; Zbl 1100.68578)
Kalnishkan, Yuri; Vovk, Volodya; Vyugin, Michael V. Loss functions, complexities, and the Legendre transformation. (English) Zbl 1069.68055 Theor. Comput. Sci. 313, No. 2, 195-207 (2004). MSC: 68Q30 PDFBibTeX XMLCite \textit{Y. Kalnishkan} et al., Theor. Comput. Sci. 313, No. 2, 195--207 (2004; Zbl 1069.68055) Full Text: DOI