“Solvable and unsolvable problems.” In Science News, 31, pp. 7-23

Melbourne, London, Baltimore: Penguin Books, 1954. FIRST EDITION, FIRST PRINTING. Original printed wrappers. First printing. This article constitutes a summary of Turing’s most theoretical work in computer science to date (a year before his death). He here expounds the ideas used in proofs of unsolvability since 1936 and enumerates some of the results and open problems. These include proof of the existence of mathematical problems that cannot be solved by the universal Turing machine. This is a turnabout from his earlier position that “any algorithmic procedure that can be carried out by a human or group of humans can be carried out by some Turing Machine.” Though common sense might say that a universal machine is impossible, Turing proved that it is possible, though later proved that there are mathematical problems which cannot be solved by any systematic method – in other words, be solved by any algorithm.

In “Solvable and unsolvable problems” Turing sets out to explain this result to a lay audience. Starting from concrete examples of problems that do admit of algorithmic solution, Turing works his way towards an example of a problem that is not solvable by any systematic method. Loosely put, this is the problem of sorting puzzles into those that will “come out” and those that will not. Turing gives an elegant argument showing that a sharpened form of this problem, which he call the “substitution type of puzzle,” is not solvable by means of a systematic method. Of interest is that his puzzle examples are quite similar to those invented by Lewis Carroll in his Doublets: a word puzzle (first published in London, 1879).

Turing suggests that any puzzle can be re-expressed as a substitution puzzle. Some row of letters can always be used to represent the “starting position” envisaged in a particular puzzle, e.g. in the case of a chess problem, the pieces on the board and their positions. Desired outcomes, for example board positions that count as wins, can be described by further rows of letters, and the rules of the puzzle, whatever they are, are to be represented in terms of permissible substitutions of groups of letters for other groups of letters. It is much easier to understand by reading the article than by reading this description.

See Turing, Alan, ‘Solvable and Unsolvable Problems (1954)’, in Copeland (ed.), The Essential Turing (Oxford, 2004; online edn, Oxford Academic, 12 Nov. 2020), https://doi.org/10.1093/oso/9780198250791.003.0024, accessed 22 Sept. 2023.