Category Archives: Math

I.J. Good on Super Intelligence

Source: Gizmodo, Oct 2013

I. J. Good happened to invent the idea of an intelligence explosion, and if it really was possible. The intelligence explosion was the first big link in the idea chain that gave birth to the Singularity hypothesis.

In the 1965 paper “Speculations Concerning the First Ultra-intelligent Machine,” Good laid out a simple and elegant proof that’s rarely left out of discussions of artificial intelligence and the Singularity:

Let an ultraintelligent machine be defined as a machine that can far surpass all the intellectual activities of any man however clever. Since the design of machines is one of these intellectual activities, an ultraintelligent machine could design even better machines; there would then unquestionably be an “intelligence explosion,” and the intelligence of man would be left far behind. Thus the first ultraintelligent machine is the last invention that man need ever make . . .

Thus the first ultraintelligent machine is the last invention that man need ever make, provided that the machine is docile enough to tell us how to keep it under control (emphasis mine).

In a 1996 interview with statistician and former pupil David L. Banks, Good revealed that he was moved to write his essay after delving into artificial neural networks. Called ANNs, they are a computational model that mimics the activity of the human brain’s networks of neurons. Upon stimulation, neurons in the brain fire, sending on a signal to other neurons. That signal can encode a memory or lead to an action, or both. Good had read a 1949 book by psychologist Donald Hebb that proposed that the behavior of neurons could be mathematically simulated.

In 1998, Good was given the Computer Pioneer Award of the IEEE (Institute of Electrical and Electronics Engineers) Computer Society. He was eighty-two years old. As part of his acceptance speech he was asked to provide a biography. He submitted it, but he did not read it aloud, nor did anyone else, during the ceremony. Probably only Pendleton knew it existed.

[The paper] “Speculations Concerning the First Ultra-intelligent Machine” (1965) . . . began:

“The survival of man depends on the early construction of an ultra-intelligent machine.” Those were his [Good’s] words during the Cold War, and he now suspects that “survival” should be replaced by “extinction.” He thinks that, because of international competition, we cannot prevent the machines from taking over. He thinks we are lemmings. He said also that “probably Man will construct the deus ex machina in his own image.”

“In mathematics the art of asking questions is more valuable than solving problems

Source: American Mathematical Monthly, Jan 2003

When he received his doctoral degree in 1866, Georg Cantor (1845-1918) followed the custom of the day by defending certain theses that he had advanced. (Hilbert was four years old at the time.) The third of these reads [9, p. 8]: “In mathematics the art of asking questions is more valuable than solving problems.”

Indeed, it is precisely by the identification of concrete problems that mathematics has been able to and will continue to develop. That is the deeper reason why Hilbert took the risk of offering a list of unsolved problems.

For the axiomatization of a theory one needs its completion. On the other hand, for the development of a mathematical theory, one needs problems. In addition to the completion of a theory, Hilbert insisted on problems and therefore on the development of a theory. In other words, Hilbert was not at all the pure formalist he is often taken to be.

In Hilbert’s formalistic view, mathematics is to be replaced by mechanical derivations of formulas, without any reasoning concerning their specific content. Recall the words of Griffith [32, p. 3]:

“A mathematical proof is a formal and logical line of reasoning that begins with a set of axioms and moves through logical steps to a conclusion …. A proof confirms truth for the mathematics.” In such a formal system, in proof theory, the subject of research is the mathematical proof itself [48, p. 413], [58:3, p. 155]. To master this subject (in the object language), one must control the field of proofs (in a metalanguage).

How many proofs do mathematicians publish each year? A back of-the-envelope calculation yields a rough approximation: multiplying the number of journals by the number of yearly issues by the number of papers per issue by the average number of theorems per paper, someone has arrived at an estimated lower bound of two hundred thousand theorems a year!

“Simplicity … is simplicity of ideas, not simplicity of a mechanical sort that can be measured by counting equations or symbols,” declared the Nobel Laureate physicist Steven Weinberg

Hilbert’s 24th Problem:

Source: Wikipedia, date indeterminate
<Original: American Mathematical Monthly, Jan 2003>

Hilbert’s twenty-fourth problem is a mathematical problem that was not published as part of the list of twenty-three problems known as Hilbert’s problems but was included in David Hilbert‘s original notes. The problem asks for a criterion of simplicity in mathematical proofs and the development of a proof theory with the power to prove that a given proof is the simplest possible.[1]

The 24th problem in my Paris lecture was to be: Criteria of simplicity, or proof of the greatest simplicity of certain proofs. Develop a theory of the method of proof in mathematics in general. Under a given set of conditions there can be but one simplest proof.

Mathematics – A Chapter in the History of Ideas

Source: IAS, Fall 2007

Robert Langlands


Jose Luis Borge’s Library of Babel

Source: The Conversation, Feb 2016

In “The Library of Babel,” the fascinating short story by Jorge Luis Borges, we learn about a certain library in which each book has 410 pages, and each page has 40 lines of 80 characters. The alphabet in use has 22 letters and three punctuation marks, making a total of 25 orthographic characters. We are told that every possible book is somewhere in this imagined library. So, how many books are there? First note that there are 410 x 40 x 80 = 1,312,000 characters in each book and since we have 25 choices for each character, there are 25¹³¹²⁰⁰⁰ possible books. As a power of 10, that’s roughly 10¹⁸³⁴⁰⁹⁷.

While we can’t possibly enumerate a catalog of all the books, we can imagine any book we like. There is a completely blank book. There is a book with a single comma in the middle of page 204 and nothing else. There are actually 1,312,000 books with a single comma and nothing else (just in each of the possible locations). There is a book with only the letter y in every spot. This article you’re reading right now appears exactly as it is written (by spelling out the numbers and ignoring extraneous punctuation) in an enormous number of books in the library (10 to a very large power, certainly more than 1.7 million). It appears in every language on the planet (suitably translated into the alphabet).

Solomonoff Induction

Source: Less Wrong, Jul 2012


1. Algorithms — We’re looking for an algorithm to determine truth.

2. Induction — By “determine truth”, we mean induction.

3. Occam’s Razor — How we judge between many inductive hypotheses.

4. Probability — Probability is what we usually use in induction.

5. The Problem of Priors — Probabilities change with evidence, but where do they start?

The Solution

6. Binary Sequences — Everything can be encoded as binary.

7. All Algorithms — Hypotheses are algorithms. Turing machines describe these.

8. Solomonoff’s Lightsaber — Putting it all together.

9. Formalized Science — From intuition to precision.

10. Approximations — Ongoing work towards practicality.

11. Unresolved Details — Problems, philosophical and mathematical.

P vs NP Talk – Avi Wigderson @ IAS