8 ms·

What Is the Point of Decidability

39 points by jjgreen 3y ago

jjgreen 3y ago
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 3y ago
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.
- garba_dlm 3y ago
  > 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 3y ago
  > 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/ https://dhall-lang.org/
- kevinventullo 3y ago
  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.”
- kryptiskt 3y ago
  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-into-nso-zero-click.html 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."
jimhefferon 3y ago
Nothing there. Hug of death?
- jjgreen 3y ago
  Looks OK to me, first time I went there there was an "are you a robot?" button, possibly enable JS?
- gwern 3y ago
  You need to click through their anti-spam mechanism (absurd as that is).
ccvannorman 3y ago
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.
- haltist 3y ago
  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.
  - haltist 3y ago
    Something else to consider is that if it is possible to truly engineer human level intelligence for operating autonomous machines then ethical concerns would require treating such systems with full human rights. Some are already claiming the ethical thresholds for human rights for AI have already been passed in internal research projects at Google.[1] 1: https://www.bbc.com/news/technology-62275326 https://www.bbc.com/news/technology-62275326
- cochne 3y ago
  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.
  - 3y ago
haltist 3y ago
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 https://lists.ugent.be/wws/arc/fom/2023-10/msg00007.html
srcreigh 3y ago
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 3y ago
  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 3y ago
    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 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.
bgilroy26 3y ago
I found this blog post helpful in trying to understand all of this https://www.digitalonus.com/the-origins-of-functional-programming/ https://www.digitalonus.com/the-origins-of-functional-progra...
woopsn 3y ago
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 https://arxiv.org/abs/1502.04135
- onesphere 3y ago
  And conservation laws, uncertainty, fate, selection, awareness. https://en.wikipedia.org/wiki/Logical_consequence https://en.wikipedia.org/wiki/Logical_consequence

39 points by jjgreen 3y ago

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 3y ago

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.

garba_dlm 3y ago
> 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 3y ago
> 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/ https://dhall-lang.org/
kevinventullo 3y ago
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.”
kryptiskt 3y ago
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-into-nso-zero-click.html 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."

jimhefferon 3y ago

Nothing there. Hug of death?

jjgreen 3y ago
Looks OK to me, first time I went there there was an "are you a robot?" button, possibly enable JS?
gwern 3y ago
You need to click through their anti-spam mechanism (absurd as that is).

ccvannorman 3y ago

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.

haltist 3y ago
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.
- haltist 3y ago
  Something else to consider is that if it is possible to truly engineer human level intelligence for operating autonomous machines then ethical concerns would require treating such systems with full human rights. Some are already claiming the ethical thresholds for human rights for AI have already been passed in internal research projects at Google.[1] 1: https://www.bbc.com/news/technology-62275326 https://www.bbc.com/news/technology-62275326
cochne 3y ago
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.
- 3y ago

haltist 3y ago

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 https://lists.ugent.be/wws/arc/fom/2023-10/msg00007.html

srcreigh 3y ago

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 3y ago
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 3y ago
  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 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.

bgilroy26 3y ago

I found this blog post helpful in trying to understand all of this https://www.digitalonus.com/the-origins-of-functional-programming/ https://www.digitalonus.com/the-origins-of-functional-progra...

woopsn 3y ago

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 https://arxiv.org/abs/1502.04135

onesphere 3y ago
And conservation laws, uncertainty, fate, selection, awareness. https://en.wikipedia.org/wiki/Logical_consequence https://en.wikipedia.org/wiki/Logical_consequence