信息、随机及不完整性INFORMATION, RANDOMNESS AND INCOMPLETENESS, 2ND ED
分類: 图书,进口原版书,科学与技术 Science & Techology ,
作者: Gregory J. Chaitin著
出 版 社: 中南工业大学出版社
出版时间: 2003-12-1字数:版次: 1页数: 319印刷时间: 1990/04/01开本:印次:纸张: 胶版纸I S B N : 9810201540包装: 精装内容简介
This book is an essential companion to Chaitin's monograph ALGORITHMIC INFORMATION
THEORY and includes in easily accessible form all the main ideas of the creator and principal archi-tect of algorithmic information theory. This expanded second edition has added thirteen abstracts, a 1988 SCIENTIFIC AMERICAN article, a transcript of a EUROPALIA 89 lecture, an essay on bi-ology, and an extensive bibliography. Its larger format makes it easier to read. Chaitin's ideas are a fundamental extension of those of Godel and Turing and have exploded some basic assumptions of mathematics and thrown new light on the scientific method, epistemology, probability theory, and of course computer science and information theory."One will find in [Information, Randomness & Incompleteness] all kinds of "articles which are popularizations or epistemological reflections, and presentations which permit one to rapidly obtain a precise idea of the subject and of some of its applications (in particular in the biological domain).
Very complete, it is recommended to anyone who is interested in algorithmic information theory." Jean-Paul Delahaye in LA RECHERCHE "No one, but no one, is exploring to greater depths the amazing insights and theorems that flow from Godel's work on undecidability than Gregory Chaitin. His exciting discoveries and speculations in-vade such areas as logic, induction, simplicity, the philosophy of mathematics and science, random-ness, proof theory, chaos, information theory, computer complexity, diophantine nalysis, and even the origin and evolution of life." Martin Gardner "Gregory Chaitin...has proved the ultimate in undecidability theorems that the logical structure of arithmetic can be random... The assumption that the formal structure of arithmeticis precise and regular turns out to have been a time-bomb, and Chaitin has just pushed the detonator." Ian Stewart in NATURE
目录
Part l--Introductory/Tutorial/Survey Papers
Randomness and mathematical proof, Scientific American, 1975
Randomness in arithmetic, Scientific American, 1988
On the difficulty of computations, IEEE Transactions on Information Theory, 1970
Information-theoretic computational complexity, IEEE Transactions on Information Theory, 1974
Algorithmic information theory, Encyclopedia of Statistical Sciences, 1982
Algorithmic information theory, IBM Journal of Research and Development, 1977
Part ll--Applications to Metamathematics
Godel's theorem and information, International Journal of Theoretical Physics, 1982
Randomness and Godel's theorem, Mondes en Developpement, 1986
An algebraic equation for the halting probability, The Universal Turing Machine, 1988
Computing the busy beaver function, Open Problems in Communication and Computation, 1987
Part Ill--Applications to Biology
To a mathematical definition of "life", A CM SICA CT News, 1970
Toward a mathematical definition of "life", The Maximum Entropy Formalism, 1979
Part IV--Technical Papers on Self-Delimiting Programs
A theory of program size formally identical to information theory, Journal of the A CM, 1975
Incompleteness theorems for random reals, Advances in Applied Mathematics, 1987
Algorithmic entropy of sets, Computers & Mathematics with Applications, 1976
Part V--Technical Papers on Blank-Endmarker Programs
Information-theoretic limitations of formal systems, Journal of the ACM, 1974
A note on Monte Carlo primality tests and algorithmic information theory, Communications on Pure and Applied Mathematics, 1978
Information-theoretic characterizations of recursive infinite strings, Theoretical Computer Science, 1976
Program size, oracles, and the jump operation, Osaka Journal of Mathematics, 1977
Part VI--Technical Papers on Turing Machines & LISP
On the length of programs for computing finite binary sequences, Journal of the ACM, 1966 .
On the length of programs for computing finite binary sequences: statistical considerations, Journal of the ACM, 1969
On the simplicity and speed of programs for computing infinite sets of natural numbers, Journal of the ACM, 1969
Part VII--Abstracts
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines, AMS Notices, 1966
On the length of programs for computing finite binary sequences by bounded-transfer Turing machines II, AMS Notices, 1966
Computational complexity and G0del's incompleteness theorem, AMS Notices, 1970
Computational complexity and Godel's incompleteness theorem, A CM SIGA CT News, 1971 ..
Information-theoretic aspects of the Turing degrees, AMS Notices, 1972
Information-theoretic aspects of Post's construction of a simple set, AMS Notices, 1972
On the difficulty of generating all binary strings of complexity less than n, AMS Notices, 1972 .
On the greatest natural number of definitional or information complexity
A necessary and sufficient condition for an infinite binary string to be recursive, Recursive Function Theory: Newsletter, 1973
There are few minimal descriptions, Recursive Function Theory: Newsletter, 1973
Information-theoretic computational complexity, IEEE International Symposium on Information Theory, 1973
A theory of program size formally identical to information theory, IEEE International Sympo- sium on Information Theory, 1974
Recent work on algorithmic information theory, IEEE International Symposium on Information Theory, 1977
Part Vlll--Bibfiography
Publications of G J Chaitin
Discussions of Chaitin's Work
Epilogue
Undecidability & randomness in pure mathematics, EUROPALIA Conference on Self-Organization, 1989
Algorithmic information & evolution, IUBS Workshop on Biological Complexity, 1988