(hi all, my favorite “haunts” in cyberspace lately seem not so busy or as engaging as in past, not sure why that is, so out of sheer lack of alternatives am going through my big link piles/ archives and finally writing up some of my big topics saved over years.)

this is a very big/ deep/ mysterious topic that have been researching and musing on for decades, almost since a teenager, starting with Hofstadters award winning/ near-legendary musings.**[a5][a6]** the topic also unifies many different threads/ post on this blog. (the delightful comic comes from a google image search result on the term “undecidability”… (*doncha just luv AI?! which maybe even could show signs of a *(great!?!)* sense of humor at times?*)

its one of those crosscutting areas where it can seem like very many people are inquiring into it, and almost nobody is, all at the same time. undecidability seems to be the extraordinary mathematical equivalent/ model of *terra incognita* aka middle age maps that stated at the edges—literally thought to be the same as the *edges of the earth or even existence*—*“here there be dragons”*.

*aka (mixed metaphor overload alert…) the lynchpin. the 3rd rail (of math/ computer science). haunted house/ mansion. the bermuda triangle. UFO. (boogeyman? monster? under the bed?) or how about some great physics analogies? dark matter/ energy? black hole(s)? etc!*

one might say this is a major phenomenon of the massive iceberg, where 90% (or more!) is unseen, or the elephant, in the aphorism about the blind men and the elephant. its a very big elephant in this case! that may even be the understatement of the year! which reminds me, as an old anecdote went in my high school calculus book (Finney?), talking about the self-referential derivative of *e ^{x}* as

*e*quoting an old joke/ legend/ folklore about what the indian guru said when asked about what held the earth, and said “an elephant”, and then asked “whats below that”, replied,

^{x},*“its elephants all the way down!”*

over the many years, have discovered there is a strong crosscutting connection between these many seemingly disparate areas of computer science in math. they are basically all united by the phenomenon of turing completeness, or the flip (dark) side, (the sheer difficulty of) undecidability. maybe in some ways have some better picture of this than others, but even my own picture is quite fragmented and cloudy at times. ie just another blind mans ramblings. (“in the kingdom of the blind, the one-eyed man is king”?)

- halting problem
- godels theorem
- undecidability
- automated theorem proving
- number theory
**[b]** - fractals
- busy beaver problem
**[c]** - program termination analysis
**[a1]** - (pseudo) random walks
- different TM complete systems eg tag systems, CAs etc
- remarkable TM complete proofs such as TM completeness in conways game of life, hilberts 10th problem by Matiyasevich, Davis, Putnam, Robinson,
**[a7]**periodic tiling problems, Cooks proof for CA 110,**[a2][d7]**etc - empirical/ experimental mathematics
- notorious/ very difficult open problems such as collatz or Riemann hypothesis which have surface aspects of pseudo-random walks

these all may not seem all that related and it could take an entire book to attempt to extricate all the deep/ subtle connections (so, beyond the scope of this blog post, which will be more like just a sketch/ survey of the tip of the iceberg).

undecidability is a phenomenon that is in a sense “much harder” than other mathematical phenomena studied. in a sense, math is the study of order, and fractals are a study of quasi-order, and undecidability is a study of the ultimate disorder, and hence the ultimate in difficulty. there is a book on collatz by Lagarias that calls it “a challenge” which is maybe the understatement of the century. (because its ~¾ century already and its still unsolved—and have been working on it myself for nearly ~⅓ of that!)

on other hand in stark contrast/ juxtaposition *undecidability* might be called *“the ultimate challenge”* or even *“the mother of all challenges”*…! there is even a sense in which it is the *only* problem, and all other problems are mere facets/ manifestations of the same problem (reminds me of the hindu concept of *maya*, aka Taoist concept of *“~10K things”*, aka buddhist *Samsara*), more on that right below!

have been looking for a way to unify all these areas. a possible unification would be some method that is shown to be powerful in attacking arbitrary undecidable problems. my strategy was to focus on the collatz problem in particular but try with an eye toward devising general techniques in attacking it. collatz seems in some sense to be the “simplest” unresolved problem in this area. so far, under a harsh analysis, the attack has mostly failed, but there are possibly some minor “spinoffs” that seem to reveal a bit more about the problem.

collatz itself may seem like a meaningless, inconsequential, or even impossible problem, but it can serve as a very hard rock to sharpen ones sword on, and sometimes have conjectured that maybe a sword exists that could cut through this problem someday. other times, on bad days, it might seem more like killer kryptonite that could even heavily debilitate a superman.

it is still against the instincts of mainstream theorists to regard all these areas as unified. have not been able to dramatically demonstrate their unification myself, but have very long noticed it. very few others are chasing it directly or are close to it. this post tries to consolidate most in the refs. the closest to another person who seems to understand it is Michel in his great/ brilliant 2013 paper.**[b2]** (coincidentally appearing nearly about ~1yr after this blog started.) it was not really noticed much but he said quite meaningfully (p3):

Actually, the halting problem for Turing machines launched on a blank tape is m-complete, and this implies that this problem is as hard as the problem of the provability of a mathematical statement in a logical theory such as ZFC (Zermelo Fraenkel set theory with axiom of choice). So, when Turing machines with more and more states and symbols are studied, potentially all theorems of mathematics will be met. When more and more non-halting Turing machines are studied to be proved non-halting, one has to expect to face hard open problems in mathematics, that is problems that current mathematical knowledge can’t settle.

there does seem to be something maybe more fundamental about number theory. as michel remarks (p33)

Many universal models of computation are known: Turing machines, tag-systems, cellular automata, Diophantine equations, etc. (see [35]). Of course, any universal model can simulate and be simulated by any other universal model. But it is Collatz-like functions, and not another model, that appear naturally in this study. Their unexpectedly pervasive presence leads to wonder about the significance of their status among mathematical beings.

tried to formulate some of this crosscutting nature in one of my cs.se answers but mostly failed at it as the feedback/ comments correctly isolate.**[e11]** but all these refs taken together hopefully paint/ evoke a better picture.

the topic shows up in many facets in many scattered stackexchange posts.**[e][f][g]**

this is “one” of the hardest theoretical problems in existence, and do believe that future mathematics might make a dent in it. have spent many years myself, and maybe have dented it, but also feel like it has more than dented me back at times. its like Nietzsches old saying/ quote, one can stare into the abyss, and the abyss stares back.

have tried to mount/ lead some collective research program/ attack in this area, and have again failed largely in that quest; although in yet another sense it is the largest collective research program in existence, except that nobody working on it realizes they are working on the same project. (it all has a very *“what is the sound of one hand clapping”* zen flavor if you havent noticed yet. because ofc zen is very deep also.)

as you might tell, this is a topic that long precedes this blog inception, “a long time in the making”, and the blog title “Turing machine” even foreshadows this post. the quest continues. its a very difficult quest that will go longer than even my own (puny) lifetime. (sometimes the vastness of the universe can make you feel very small, and mathematics is a very big universe that sometimes feels even bigger or more vast than even the physical one! a place where one can get lost in space forever—*infinitely long* so to speak!)

also, coincidence! did not plan this but this is the ** 100^{th} post** on this blog! 😮 😀 😎 ⭐ ❤ 💡 ❗

**a. decide**

- 1. Proving Program Termination | May 2011 | Communications of the ACM
- 2. Rule 110 – Wikipedia, the free encyclopedia
- 3. Universality of Wolfram’s 2, 3 Turing Machine / Alex Smith
- 4. Accidentally Turing-Complete ― Andreas Zwinkau
- 5. Gödel, Escher, Bach: An Eternal Golden Braid: Douglas R. Hofstadter: 9780465026562: Amazon.com: Books
- 6. Metamagical Themas: Questing For The Essence Of Mind And Pattern: Douglas Hofstadter: 9780465045662: Amazon.com: Books
- 7. Hilbert’s tenth problem – Wikipedia, the free encyclopedia

**b. number theory**

- 1. modeling – machine learning applications in number theory – Cross Validated
- 2. Problems in number theory from busy beaver competition, Michel
- 3. reference request – Is computer science a branch of mathematics? – Mathematics Stack Exchange
- 4. soft question – Why are mathematical proofs that rely on computers controversial? – Mathematics Stack Exchange
- 5. nt.number theory – Fractal-like structures arising from the action of a group on $\mathbb{Z}^2$ – MathOverflow
- 6. co.combinatorics – Why can machine learning not recognize prime numbers? – Theoretical Computer Science Stack Exchange
- 7. proofs – Is it worthwhile to try to prove a conjecture by mapping it to a Turing machine? – Theoretical Computer Science Stack Exchange
- 8. The Undecidability of the Generalized Collatz Problem – Springer
- 9. nt.number theory – Fractal-like structures arising from the action of a group on $\mathbb{Z}^2$ – MathOverflow
- 10. co.combinatorics – Why can machine learning not recognize prime numbers? – Theoretical Computer Science Stack Exchange
- 11. Open Problems That Might Be Easy | Gödel’s Lost Letter and P=NP

**c. busy beaver**

- 1. The Busy Beaver Problem : A NEW MILLENNIUM ATTACK
- 2. computability – Computation of busy beaver function – Computer Science Stack Exchange
- 3. computability – Is busy beaver the fastest growing function known to man? – Computer Science Stack Exchange
- 4. Busy beavers gone wild / Lafitte
- 5. Small Turing machines and generalized busy beaver competition / Michel
- 6. Looking for Busy Beavers. A socio-philosophical study of a computer-assisted proof. / De Mol
- 7. The Busy Beaver Problem | Gödel’s Lost Letter and P=NP
- 8. computability theory – Busy Beaver modulo 2 – MathOverflow
- 9. Where Hard Meets Easy | Gödel’s Lost Letter and P=NP
- 10. computability – What properties of busy beaver numbers are computable? – Mathematics Stack Exchange
- 11. Looking for Busy Beavers. A socio-philosophical study of a computer-assisted proof. / De Mol

**d. papers**

- 1. tackling posts correspondence problem [zhao]
- 2. [math/0504351] The halting problem is decidable on a set of asymptotic probability one
- 3. On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results. / De Mol
- 4. The complexity of small universal Turing machines: a survey / Woods, Neary
- 5. Search-Based Ambiguity Detection in Context-Free Grammars / Vasudevan1 & Tratt
- 6. TURING MACHINES TO WORD PROBLEMS
- 7. Universality in Elementary Cellular Automata / Cook
- 8. [1407.1891] On Termination of Integer Linear Loops
- 9. Proving program termination
- 10. Evaluating the Complexity of Mathematical Problems: Part 1 / Calude
- 11. Evaluating the Complexity of Mathematical Problems: Part 2 / Calude
- 12. [1308.4678] Post-human mathematics

**e. cs.se**

- 1. Algorithm to test whether a language is context-free – Computer Science Stack Exchange
- 2. computability – Algorithm to solve Turing’s “Halting problem” – Computer Science Stack Exchange
- 3. computability – Ratio of decidable problems – Computer Science Stack Exchange
- 4. probability theory – Possible to construct a probabilistic halting problem solver? – Computer Science Stack Exchange
- 5. reference request – Computational approach deciding whether a set of Wang Tile could tile the space up to some size – Computer Science Stack Exchange
- 6. turing machines – Program synthesis, decidability and the halting problem – Computer Science Stack Exchange
- 7. computability – Why, really, is the Halting Problem important? – Computer Science Stack Exchange
- 8. computability – Why can’t we solve the Halting Problem by using Artificial Intelligence? – Computer Science Stack Exchange
- 9. turing completeness – Is the unsolvability of the N-Body Problem equivalent to the Halting Problem – Computer Science Stack Exchange
- 10. computability – Unprovable Post correspondence problem instance – Computer Science Stack Exchange
- 11. turing machines – What are the simplest examples of programs that we do not know whether they terminate? – Computer Science Stack Exchange
- 12. computability – Human computing power: Can humans decide the halting problem on Turing Machines? – Computer Science Stack Exchange
- 13. computability – Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility? – Computer Science Stack Exchange
- 14. formal languages – Ambiguous context free – Computer Science Stack Exchange
- 15. computability – Problems whose decidability status is unknown but known to be less hard than the halting problem – Computer Science Stack Exchange
- 16. Is the halting problem always decidable for non-universal programs?

**f. tcs.se**

- 1. computability – A simple problem whose decidability is not known – Theoretical Computer Science Stack Exchange
- 2. computability – density of undeciability – Theoretical Computer Science Stack Exchange
- 3. computability – Is there a sensible notion of an approximation algorithm for an undecidable problem? – Theoretical Computer Science Stack Exchange
- 4. fl.formal languages – Asymptotic density of ambiguous context-free grammars (CFGs) – Theoretical Computer Science Stack Exchange
- 5. halting problem – What is the smallest Turing machine where it is unknown if it halts or not? – Theoretical Computer Science Stack Exchange
- 6. reference request – loop invariants in proving program termination – Theoretical Computer Science Stack Exchange
- 7. reference request – research on systematically attacking multiple instances of undecidable problems – Theoretical Computer Science Stack Exchange
- 8. a small C-like language that turing machines can simulate – Theoretical Computer Science Stack Exchange
- 9. (False?) proof for computability of a function? – Theoretical Computer Science Stack Exchange

**g. mo/math.se**

- 1. logic – Have we found a Turing Machine for which halting/non-halting is unprovable? – Mathematics Stack Exchange
- 2. ds.dynamical systems – Undecidability in Conway’s Game of Life – MathOverflow
- 3. lo.logic – How undecidable is the spectral gap? – MathOverflow
- 4. lo.logic – What is the relationship between Turing Machines and Gödel’s Incompleteness Theorem? – MathOverflow