[HN Gopher] What Is the Point of Decidability
___________________________________________________________________
What Is the Point of Decidability
Author : jjgreen
Score : 26 points
Date : 2023-10-05 09:14 UTC (13 hours ago)
(HTM) web link (lists.ugent.be)
(TXT) w3m dump (lists.ugent.be)
| ccvannorman wrote:
| Startup founder to VC: We're going to build an AI that can do X!
|
| 1 billion dollars later: We discovered we can't do X because
| there's this thing called "undecidability."
|
| Undecidability puts fundamental limits on what we can do with
| computers. You can't even do simple things like write a program
| which can { determine if two programs are equal, determine if two
| programs would have equal outputs given any input, if any program
| will return a "1", if any program would halt, ... }
|
| This feels kinda important considering what people might try to
| build using AI.
| cochne wrote:
| You can certainly write a program which can determine if a
| program would halt. It just won't be able to output a yes or no
| for _every_ program. In some cases it would have to output
| 'undecidable'. Most of the practical programs you might want to
| feed into this program will have an answer.
| trehalose wrote:
| If I may nitpick, it shouldn't ever output "undecidable" but
| rather something like "undecided" or "I give up". A program
| that can be trivially seen to halt if we let it run for a
| quadrillion years is only "undecidable" in the sense that we
| might get impatient and die.
| haltist wrote:
| For practical purposes it doesn't really matter because most
| real world computation is an approximation anyway. AI
| researchers don't care much about impossibility results because
| their goal is human level artificial intelligence and they
| consider people to be existence proofs that such computation is
| possible to engineer artificially. Basically, AI researchers
| believe that people are just walking computers/robots so
| they're not at all concerned about theoretical obstructions to
| constructing generally intelligent software systems.
| bgilroy26 wrote:
| I found this blog post helpful in trying to understand all of
| this
|
| https://www.digitalonus.com/the-origins-of-functional-progra...
| srcreigh wrote:
| I prefer busy beaver numbers to undecidability. The halting
| problem has a flaw in that it asks for finite code to predict
| halting for any arbitrary program, which to me seems intractable
| despite the logical paradoxes involved.
|
| Busy beaver numbers step around this by looking at TMs of one
| size at a time.
|
| Now, the busy beaver numbers are enormous and we will likely
| never solve even BB(6). But that's not for reasons of logical
| paradoxes like "this sentence is false" or "the smallest positive
| integer not definable in under sixty letters".
|
| The reasons we can't solve small busy beaver numbers:
|
| - There's an enourmous number of 6-state TMs let alone 100 state
| TMs.
|
| - BB(6) has been proven to be at least 10^10^10^...^10 (15 times
| total). So what could BB(20) be.
|
| - some small busy beaver numbers are conjectured to be
| independent of ZFC, meaning we'd need new math foundations.
| Conjectured to be BB(20), proven at least as high as BB(745) is
| independent of ZFC.
|
| - various unsolved math problems are equivalent to TMs of
| particular sizes: Goldbach's conjecture, Riemann hypothesis, etc
|
| At least with busy beaver numbers there isn't some stupid
| paradox, we just can't practically solve them.
| cvoss wrote:
| But BB is an uncomputable function. You've not escaped
| undecidability at all. You cannot write a program that will
| compute BB(n) given n as an input.
|
| Also, the enormous size of BB(n) for any particular n is no
| argument for why it's so hard to determine what BB(n) is. It's
| actually the other way around. Undecidability sheds light on
| the enormous sizes of BB(n). Suppose you had a computable
| function which was known to be an upper bound for BB. Well,
| then you can play some tricks and leverage it to solve the
| halting problem by simulating machines for only so many steps
| before realizing whether you're looking at a halting one or a
| non-halting one. Therefore, no such upper bound function
| exists. Therefore, you can write down the fastest growing
| computable function you can think of, and BB will outpace it.
| srcreigh wrote:
| Scott Aaronson addresses this. Uncomputable does _not_ mean
| unsolvable by humans. It just means there's no axiomatic
| system powerful enough to enumerate all the busy beaver
| numbers. Rather we'll need axiomatic system A for the first
| few, then B, then C, etc each more complicated than the last.
|
| Ex: we already know BB(745) is independent of ZFC, any more
| powerful system should have its own independence limit, etc.
|
| source: page 6 here
| https://www.scottaaronson.com/papers/bb.pdf
|
| Since BB computing code is halting problem solving code, it
| goes back to my point about "one finite program to solve
| halting for countably infinitely many TMs and inputs" seeming
| intractable compression-wise. On the contrary, maybe
| countably many BB computing programs for each countably many
| BB number would be doable.
| cvoss wrote:
| > Uncomputable does not mean unsolvable by humans.
|
| It absolutely means that, unless you don't believe the
| Church-Turing thesis and claim that humans have the ability
| to carry out computations that machines physically cannot.
|
| I think you are misunderstanding the difference between
| having an algorithm to determine BB(n) for all n, and
| figuring out what BB(n) is for certain special n.
| srcreigh wrote:
| f(n) = name of top pop song in the year n defined for
| n>=1950
|
| This doesn't seem computable, yet we can definitely
| figure out its values.
|
| Anyways, I believe my point above is in alignment with
| Scott Aaronson, so if you've read that I'm curious what
| you think the differences are.
| ogogmad wrote:
| That's an irrelevant example because your f(n) does not
| have a self-contained mathematical definition.
| [deleted]
| tshaddox wrote:
| If you're trying to teach or learn about undecidability, I've
| always thought of busy beaver problems as unnecessary added
| complexity over the halting problem. I can't think of a good
| way to explain the undecidability of busy beaver without
| invoking the halting problem. It's not because there is an
| enormous number of 6-state TMs or because BB(6) is at least
| 10^10^10^...^10. It's simply because you can't decide, for each
| TM with n states, whether that TM will halt.
|
| Busy beaver problems are interesting in their own right,
| particularly for 1) demonstrating the huge amount of complexity
| that can arise from very simple rules and 2) for the epiphany
| that a busy beaver function grows asymptotically faster than
| _any_ computable. But I don 't find them to be great as an
| introduction to undecidability.
| kevinventullo wrote:
| I also prefer BB's, I think because the rapid increase in scale
| gives me an almost supernatural or divine feeling. As you said,
| "smallish" BB's already transcend ZFC, which is something like
| humanity's best attempt at "universal" logical foundations. So,
| when thinking about BB's, I can't help but feel that I'm
| running up against the limits of what is even possible for
| humans to comprehend.
| jjgreen wrote:
| A posting on the foundations of mathematics mailing list, a
| rather nice high-level view I thought. The whole thread is worth
| a read ...
| ryangs wrote:
| I think there is a fundamental gap between the OP's concept of
| "Point" versus the responders. They're essentially asking if
| decidability has practical[1] uses to which the answer is
| generally "No". When a general CS practitioner imagines doing
| something via computation, they are already thinking of things in
| the realm of the possible. It may be helpful to know that exact
| answers are intractable and you'll have to settle for an
| approximation, but that information seems to correlate more with
| complexity than with decidability.
|
| [1]: Where practical is in the sense of an engineer (or in their
| terms, a CS practitioner), not a theoretician. Most of the
| responders seem to interpret practical in the sense of a
| mathematician.
| kevinventullo wrote:
| _They 're essentially asking if decidability has practical[1]
| uses to which the answer is generally "No"._
|
| I don't think I agree! For example, I strongly suspect that
| Malware detection researchers would be following many fruitless
| paths in the vein of "Let's just figure out what the program is
| doing" if not guided by the fact that this is strictly harder
| than "Let's just figure out if the program halts."
| garba_dlm wrote:
| > _they are already thinking of things in the realm of the
| possible._
|
| very astute observation. Now I'm left wondering how this comes
| to be?
|
| what is it about the way in which a general CS practitioner's
| approach to problem solving that grounds the potential ideas
| (of how to solve problem) into the computationally decidable?
| baq wrote:
| > Where practical is in the sense of an engineer (or in their
| terms, a CS practitioner),
|
| Configuration processing. E.g. I'd like my yamls to be
| decidable, though I'll settle for guaranteed to halt[1].
|
| [1] https://dhall-lang.org/
| kryptiskt wrote:
| Decidability has very practical applications. There have been a
| number of security exploits that have depended on the attacker
| being able to run a weird machine inside a decoder of some
| kind, like NSO's iPhone hack:
|
| https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...
|
| "JBIG2 doesn't have scripting capabilities, but when combined
| with a vulnerability, it does have the ability to emulate
| circuits of arbitrary logic gates operating on arbitrary
| memory. So why not just use that to build your own computer
| architecture and script that!? That's exactly what this exploit
| does. Using over 70,000 segment commands defining logical bit
| operations, they define a small computer architecture with
| features such as registers and a full 64-bit adder and
| comparator which they use to search memory and perform
| arithmetic operations. It's not as fast as Javascript, but it's
| fundamentally computationally equivalent.
|
| The bootstrapping operations for the sandbox escape exploit are
| written to run on this logic circuit and the whole thing runs
| in this weird, emulated environment created out of a single
| decompression pass through a JBIG2 stream. It's pretty
| incredible, and at the same time, pretty terrifying."
| haltist wrote:
| Pratt gives a very good answer with a historical overview of the
| main characters and their theorems on incompleteness:
| https://lists.ugent.be/wws/arc/fom/2023-10/msg00007.html
| jimhefferon wrote:
| Nothing there. Hug of death?
| jjgreen wrote:
| Looks OK to me, first time I went there there was an "are you a
| robot?" button, possibly enable JS?
| gwern wrote:
| You need to click through their anti-spam mechanism (absurd as
| that is).
| woopsn wrote:
| One response brings up the (un)decidability of determining if a
| physical system's ground state is separated from the rest of its
| spectrum:
|
| > And there are still cases going on today where undecidability
| results are of broad interest to those outside of logic. For
| example, the "spectral gap problem" in physics asked whether,
| given a description of a physical system, whether that system
| requires a minimum amount of energy to nudge it out of its ground
| state, or whether arbitrarily small amounts of energy can nudge
| it out of its ground state. This was proven to be undecidable in
| 2015, basically telling physicists that a theoretical problem of
| theirs, motivated entirely by physical considerations, is
| hopeless in full generality.
|
| Well that sucks.[1] But I think it's cool that theoretical
| physics and theoretical computer science seem to meet together in
| these low places. Information has thermodynamic consequences and
| vice versa.
|
| [1] https://arxiv.org/abs/1502.04135
___________________________________________________________________
(page generated 2023-10-05 23:01 UTC)