Computably Enumerable Instantaneous Codes
作者： Cristian S. Calude
DOI: 10.1007/978-3-662-04978-5_4
关键词:
摘要: In this chapter — which is basically technical we present two main tools used to design Chaitin computers and consequently establish upper bounds: the extension of Kraft condition (see Theorem 2.8) arbitrary c.e. sets relativized computation. New formulae, closely analogous expressions in classical information theory, are derived.
springer.com
sci-hub.st 参考文章(33)
C.S Calude, H Ishihara, T Yamaguchi, Minimal Programs Are Almost Optimal Department of Computer Science, The University of Auckland, New Zealand. ,(1999)
C Calude, C Grozea, Kraft-Chaitin Inequality Revisited Journal of Universal Computer Science. ,vol. 2, pp. 306- 310 ,(1996)
William Lawrence Gewirtz, Investigations in the Theory of Descriptive Complexity ,(2011)
Karl Svozil, Quantum Information Theory. Journal of Universal Computer Science. ,vol. 2, pp. 311- 346 ,(1996)
Karl Svozil, Randomness And Undecidability In Physics ,(1993)
Arto Salomaa, Computation and automata ,(1985)
Cristian Grozea, Free-Extendible Prefix-Free Sets and an Extension of the Kraft-Chaitin Theorem Journal of Universal Computer Science. ,vol. 6, pp. 130- 135 ,(1999)
M. Li, P.M.B. Vitanyi, Combinatorics and Kolmogorov complexity structure in complexity theory annual conference. pp. 154- 163 ,(1991) , 10.1109/SCT.1991.160256
David Ruelle, Chance and Chaos ,(1991)
Gavriel Segre, The definition of a random sequence of qubits: from Noncommutative Algorithmic Probability Theory to Quantum Algorithmic Information Theory and back arXiv: Quantum Physics. ,(2000)