“On Unsettleable Arithmetical Problems”, 2013 (; backlinks):
It has long been known that there are arithmetic statements that are true but not provable, but it is usually thought that they must necessarily be complicated. In this paper, I shall argue that these wild beasts may be just around the corner.
…What are the simplest true assertions that are neither provable nor disprovable? I shall use the term unsettleable because for more than a century the ultimate basis for proof has been set theory. For some of my examples, it might even be that the assertion that they are not provable is not itself provable and so on. Of course this means that you shouldn’t expect to see any proofs! My examples are inspired by the Collatz 3n + 1 Problem.
…There is an explicit game with 24 simple linear functions for which there are numbers n for which the game never stops, but this is not provable. Gödel’s famous Incompleteness Theorem, published in 1931, shows that no consistent system of axioms can prove every true arithmetical statement. In particular, it cannot prove an arithmetized version of its own consistency statement. Turing translated this into his theorem about computation—that the Halting Problem for an idealized model of computation is undecidable.
Given these stupendous results, it is comparatively trivial to produce an unsettleable Collatzian game. In a 1972 paper “Unpredictable Iterations”, I showed that any computation can be simulated by a Collatzian game of a very simple type.
View PDF: