Coping with Undecidability

post by Morpheus · 2022-01-27T10:31:00.520Z · LW · GW · 13 comments

Contents

  Motte-and-Bailey computability
    Motte:
    Bayley:
      Implicitly implied:
      Even more implicitly implied, perhaps at least something I fell for:
    How to actually deal with undecidability in practice
  Further Interesting resources/Footnotes
None
13 comments

Mostly just reflections on things I've been learning about theory of computer science and trying to figure my philosophical stance towards them, in order to not be a trollable mathematician [LW · GW]

In the last few months, my mind has constantly been trying to argue against something like the "naive Church Turing Thesis" in an attempt to better understand what it means for "the real world" that some things we can ask ourselves with a Turing machine can't be answered with "yes" or "no" by any Turing machine (formally called an undecidable problem). (See the halting problem, for an example).

My confusion stems from this weird dichotomy^[1] that basically everything we can compute in the real world can be computed by a finite state automaton, because our world does not contain infinite memory tapes (as far as I know from the probabilistic evidence I was able to gather). But (for convenience?), mathematicians/computer scientists use Turing machines/Lambda Calculus/(your favorite programming language) for most purposes instead to model things, even though they have these really peculiar undecidability properties.

What I've learned so far is that applying your formal model of computation to say things about problems in the real world is a super philosophically slippery domain (though I feel the reason for this has more to do with the space of all algorithms just being a really resistant hydra and less with peculiarities of the human mind^[2]). The replies [LW · GW] I got [LW · GW] from people on Lesswrong along with Scott Aaronsons writing have been very helpful here^[3].

Maybe I am just a pedant, but after tripping myself for a while, I see other people commit philosophical blunders in this area. As an example, here is this motte-and-bailey ^[4]which I fell for [LW · GW]:

Motte-and-Bailey computability

Motte:

"intuitively computable" => a (Turing Machine)/(Lambda Calculus)/(Your favorite equivalent model $C$) can do it. The converse does not necessarily hold, because no one has infinite memory. When doing theoretical computer science, we want to abstract away the details, so it is convenient to use $C$ to be able to extrapolate Algorithm $X$ to infinity in order to force us to characterize how $X$ is behaving asymptotically (which is itself of course only a convenient way to roughly characterize the runtime of an algorithm).

Bayley:

"Let me show you a problem that even computers can't solve": "shows the halting problem"

=> modus tollens, because $C$ cannot do it => "not something you can solve (in this absolutely general case) with a computer"

Implicitly implied:

=> There are some basic things that you cannot do with a computer.

Even more implicitly implied, perhaps at least something I fell for [LW · GW]:

The version of this problem (not fully general) you'd actually care about is hard. Say that two pieces of code are indeed equivalent, or type checking. While this might not work in the general case, there obviously are heuristics that do, otherwise people wouldn't be able to write code in typed languages or do "anything at all in math/logic".

How to actually deal with undecidability in practice

I felt there was something deeply unsatisfying about the whole issue. As long as your Turing machines have finite memory, they are actually finite state automatons whose behavior is perfectly decidable. For more practical purposes, it's like saying, "your computer isn't able to print all the digits of pi!" Yes, I already knew that, thank you! But why should I care if I can calculate it to an arbitrary/sufficient precision? ^[5] Doron Zeilberger expresses this more succinctly:

The very notion of "Turing machine" is flawed, since it assumes "infinite tape". Also the "halting problem" is meaningless, as stated (so it is not surprising that it is "undecidable"). The question "does the program halt" is the same as "does there exist an integer N such that the program halts in less than N steps?", and it is tacitly assumed that N can be anything, i.e. taken over the "infinite" set of positive integers.

This seemed appealing as I could not figure out what is wrong with the above, but there are people who already did more reflection on this than I have, Scott Aaronson:

Like most of Zeilberger’s “opinions,” that one strikes me as so egregiously wrong that one wonders to what extent he himself believes it, and to what extent he just likes throwing bombs at the “mathematical establishment.”

Let M be a Turing machine that enumerates all ZF proofs, and halts iff it finds a proof of 0=1. Then “M never halts” is a perfectly-meaningful statement (it even makes a falsifiable prediction about an actual computer program—what more could you want?), which happens not to be provable in ZF assuming ZF’s consistency.

By contrast, “M tastes like chicken” is a meaningless statement.

Putting both of these statements into the same category (“meaningless”) strikes me as a bizarre twisting of language in the service of an ideology (something I don’t like even for good ideologies!). Indeed, a moment’s thought reveals that, if Zeilberger’s suggestion were adopted, mathematicians would immediately start working around it with circumlocutions (“meaningless in the sense of not provable in ZF” vs. “meaningless in the sense of meaningless”).

My problem with the above is that I still don't think I understand the implications. "How do axioms interact with the real world exactly?" is a question I don't have a good cached answer for.

At the moment the thing I reach for when I need to sleep at night is something like "ok even if some things are undecidable, and I don't really understand all the implications of this, but least I can go meta, spot the patterns and put probabilities on things." ^[6].

If you read this far, you've probably also thought about these thinking about these things sometimes. I'd be really interested to hear other people's stances on these topics. Please do share any thoughts or resources you've found "deconfusing" on your way in the comments!

Further Interesting resources/Footnotes

While writing this I also stumbled on Scott Aaronson's Thesis which is going in a similar direction (though he seems to be more concerned in characterizing what quantum computers should be capable of).

Scott Aronsons Paper on the busy beaver frontier was pretty shocking in how few states you need to make incomprehensible or even undecidable questions with a Turing machine.

---

1. I'd super interested in anyone pointing to resources that resolve this issue ↩︎

2. I know confusion is in the mind, by the way Yudkowsky makes a similar point here [LW · GW] ↩︎

3. I'll mention work from Scott Aaronson a lot, because I keep stumbling over them and noticing how these answer exactly the question I had and some I didn't even know I had them (If you feel this is excessive, and I've missed more insightful resources by other authors, Please share them in the comments, I'd love to know about them!). ↩︎

4. A motte-and-bayley refers to the situation where you use a defensible version of your views (the motte) when actively being critiqued to be able to advance the actually interesting, but "indefensible version when no one's watching" (the bailey). ↩︎

5. And yes then there is the whole "what is efficiently computable?" question, but I felt complexity classes were not as prone to philosophical blundering, and this is already rather long. ↩︎

6. A good example that I stumbled upon while writing this that made me less confused around "how do axiomatized systems interact to the real world" and how to actually cope with undecidability is Scott Aaronson arguing for why a proof of P!=NP should not be independent of ZFC(page 26-27 Section "Independent of set theory?") ↩︎

13 comments

Comments sorted by top scores.