for minimal lineal grammars," Information and Control 6:2, 117–125, also reference on p. 402 ibid: Greibach [1968] "A note on undecidable properties of formal languages", Math Systems Theory 2:1, 1–6.) Penrose tiling questions. Question of solutions for Diophantine equations and the resultant answer in the MRDP Theorem; see entry below. String compressibility: Chaitin's proof For an exposition suitable for non-specialists, see Beltrami p. 108ff. Also see Franzen Chapter 8 pp. 137–148, and Davis pp. 263–266. Franzén's discussion is significantly more complicated than Beltrami's and delves into Ω—Gregory Chaitin's so-called "halting probability". Davis's older treatment approaches the question from a Turing machine viewpoint. Chaitin has written a number of books about his endeavors and the subsequent philosophic and mathematical fallout from them. A string is called (algorithmically) random if it cannot be produced from any shorter computer program. While most strings are random, no particular one can be proved so, except for finitely many short ones: "A paraphrase of Chaitin's result is that there can be no formal proof that a sufficiently long string is random..." Beltrami observes that "Chaitin's proof is related to a paradox posed by Oxford librarian G. Berry early in the twentieth century that asks for 'the smallest positive integer that cannot be defined by an English sentence with fewer than 1000 characters.' Evidently, the shortest definition of this number must have at least 1000 characters. However, the sentence within quotation marks, which is itself a definition of the alleged number is less than 1000 characters in length!". Integer solutions of Diophantine equations: Hilbert's tenth problem The question "Does any arbitrary Diophantine equation have an integer solution?" is undecidable. That is, it is impossible to answer the question for all cases. Franzén introduces Hilbert's tenth problem and the MRDP theorem (Matiyasevich-Robinson-Davis-Putnam theorem) which states that "no algorithm exists which can decide whether or not a Diophantine equation has any solution at all". MRDP uses the undecidability proof of Turing: "... the set of solvable Diophantine equations is an example of a computably enumerable but not decidable set, and the set of unsolvable Diophantine equations is not computably enumerable". In social science In political science, Arrow's impossibility theorem states that it is impossible to devise a voting system that satisfies a set of five specific axioms. This theorem is proved by showing that four of the axioms together imply the opposite of the fifth. In economics, Holmström's theorem