undecidability: the ULTIMATE challenge

1 Reply

(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.)

calvin_undeadthis 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 ex as ex, 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, “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 100th post on this blog! 😮 😀 😎 ⭐ ❤ 💡 ❗

 

a. decide
b. number theory
c. busy beaver
d. papers
e. cs.se
f. tcs.se
g. mo/math.se

1 thought on “undecidability: the ULTIMATE challenge”

Leave a comment