By Gregory J Chaitin, Paul Davies

Dr Gregory Chaitin, one of many world's prime mathematicians, is healthier identified for his discovery of the striking omega quantity, a concrete instance of irreducible complexity in natural arithmetic which indicates that arithmetic is infinitely advanced. during this quantity, Chaitin discusses the evolution of those rules, tracing them again to Leibniz and Borel in addition to Gödel and Turing. This ebook comprises 23 non-technical papers by means of Chaitin, his favourite educational and survey papers, together with Chaitin's 3 medical American articles. those essays summarize a life-time attempt to take advantage of the idea of program-size complexity or algorithmic info content material so one can shed additional mild at the primary paintings of Gödel and Turing at the limits of mathematical equipment, either in common sense and in computation. Chaitin argues right here that his information-theoretic method of metamathematics indicates a quasi-empirical view of arithmetic that emphasizes the similarities instead of the variations among arithmetic and physics. He additionally develops his personal model of electronic philosophy, which perspectives the whole universe as an enormous computation, and speculates that maybe every thing is discrete software program, every little thing is 0's and 1's. Chaitin's primary mathematical paintings may be of curiosity to philosophers inquisitive about the boundaries of information and to physicists drawn to the character of complexity.

Show description

Read or Download Thinking about Godel and Turing: Essays on complexity, 1970-2007 PDF

Best logic books

Statistical Estimation of Epidemiological Risk (Statistics in Practice)

Statistical Estimation of Epidemiological Risk provides assurance of crucial epidemiological indices, and contains fresh advancements within the field. A useful reference resource for biostatisticians and epidemiologists operating in ailment prevention, because the chapters are self-contained and have a variety of genuine examples.

An Invitation to Formal Reasoning

This paintings introduces the topic of formal good judgment when it comes to a method that's "like syllogistic logic". Its process, like outdated, conventional syllogistic, is a "term logic". The authors' model of common sense ("term-function logic", TFL) stocks with Aristotle's syllogistic the perception that the logical different types of statements which are excited by inferences as premises or conclusions might be construed because the results of connecting pairs of phrases by way of a logical copula (functor).

Extra resources for Thinking about Godel and Turing: Essays on complexity, 1970-2007

Sample text

If one uses the methods of reasoning accepted by Hilbert, there is an upper bound to the complexity that it is possible to prove that a particular string has. This is the surprising result that we wished to obtain. Most strings of length n are of complexity approximately n, and a string generated by tossing a coin will almost certainly have this property. Nevertheless, one cannot exhibit individual examples of arbitrarily complex strings using methods of reasoning accepted by Hilbert. 1 In 1931 G¨odel questioned Hilbert’s ideas in a similar way [1], [2].

For although general relativity is considered to be the simple theory par excellence, very extended calculations are necessary to make predictions from it. Instead, one refers to the number of arbitrary choices that have been made in specifying the theoretical structure. One is naturally suspicious of a theory whose number of arbitrary elements is of an order of magnitude comparable to the amount of information about reality that it accounts for. 6 We will develop the following thesis. Call an infinite set of natural numbers perfect if there is no essentially quicker way to compute infinitely many of its members than computing the whole set.

SMC-4, pp. 88–94, Jan. 1974. [16] H. , Theory of Recursive Functions and Effective Computability. New York: McGraw-Hill, 1967. Randomness and mathematical proof Although randomness can be precisely defined and can even be measured, a given number cannot be proved to be random. This enigma establishes a limit to what is possible in mathematics. Almost everyone has an intuitive notion of what a random number is. For example, consider these two series of binary digits: 01010101010101010101 01101100110111100010 The first is obviously constructed according to a simple rule; it consists of the number 01 repeated ten times.

Download PDF sample

Rated 4.87 of 5 – based on 34 votes