First English translation of revolutionary paper that established that even in elementary parts of arithmetic, there are propositions which cannot be proved or disproved within the system. Introduction by R. B. Braithwaite.

We present a critical discussion of the claim (most forcefully propounded by Chaitin) that algorithmic information theory sheds new light on Godel's first incompleteness theorem.