For example, think of the Collatz Conjecture. It’s an extremely simple statement that could easily pop up in a “messy” computational system...and we totally can’t prove anything about it!
This is sloppily presented and false as currently written, and in any case doesn’t support the argument it’s being used for.[1] As a sample illustration of “something” we can prove about it, for all sufficiently large n, at least n0.84 integers between 1 and n eventually reach 1 once the algorithm is applied to them.[2] There have been other important results on this topic over the years,[3] though of course the conjecture itself hasn’t yet been resolved.
I’m sure there have to be examples out there of “simple” dynamical systems or related mathematical objects that we can’t prove anything interesting about,[4] but this one ain’t it.
Though, as per the conservation of expected evidence, seeing that the example chosen to support of a thesis is incorrect results in a downwards update on both the validity of the thesis and on its relevance. Likely low in magnitude in this case
Thanks for pointing out my imprecise statement there! What I meant of course “is we can’t prove the Collatz Conjecture” (which is a simple statement about a simple dynamic system), but I wrote something that doesn’t precisely say that, so apologies for that.
The main thing I intended to convey here is that the amounts of effort going into proving simple things (including the things you have mentioned that were in fact proven!) are often extremely unintuitively high to people not familiar with this, and that this happens all over CS and math.
I found Connor’s text very helpful and illuminating!
…But yeah, I agree about sloppy wording.
Instead of “you want to prove even minimal things about it” I think he should have said “you want to prove certain important things about it”. Or actually, he could have even said “you want to have an informed guess about certain important things about it”. Maybe a better example would be “it doesn’t contain a backdoor”—it’s trivial if you’re writing the code yourself, hard for a binary blob you find on the internet. Having access to someone else’s source code helps but is not foolproof, especially at scale, (e.g.).
Well, hmm, I guess it’s tautological that if you’re writing your own code, you can reliably not put backdoors in it. There’s no such thing as an “accidental backdoor”. If it’s accidental then you would call it a “security flaw” instead. But speaking of which, it’s also true that security flaws are much easier to detect or rule out if you’re writing the code yourself than if you find a binary blob on the internet.
Or the halting problem: it’s super-easy to write code that will definitely halt, but there are at least some binary blobs for which it is impossible in practice to know or even guess whether it will halt or not.
…Also, while we’re nitpicking, Connor wrote “175B FP numbers generated by unknown slop methods”. I would have instead said “175B FP numbers generated by gradient descent on internet text” or “175B FP numbers generated by a learning algorithm with no known security-related invariants” or something. (“Unknown” is false and “slop” seems to be just throwing shade (in this context).)
My impression is that if you walk of to a security researcher and say “hey what do you call the kind of thing where for example you’re not properly escaping strings embedded in other strings, like SQL injection?”, they probably wouldn’t say “oh that thing is called an accidental backdoor”, rather they would say “oh that thing is called a security vulnerability”.
(This is purely a terminology discussion, I’m sure we agree about how SQL injection works.)
I guess “backdoor” suggests access being exclusive to person who planted it, while “vulnerability” is something exploitable by everyone? Also, after thinking a bit more about it, I think you’re right that “backdoor” implies some intentionality, and perhaps accidental backdoor is an oxymoron.
This is sloppily presented and false as currently written, and in any case doesn’t support the argument it’s being used for.[1] As a sample illustration of “something” we can prove about it, for all sufficiently large n, at least n0.84 integers between 1 and n eventually reach 1 once the algorithm is applied to them.[2] There have been other important results on this topic over the years,[3] though of course the conjecture itself hasn’t yet been resolved.
I’m sure there have to be examples out there of “simple” dynamical systems or related mathematical objects that we can’t prove anything interesting about,[4] but this one ain’t it.
Something something local validity is the key to sanity and civilization
Source
Example source
Though, as per the conservation of expected evidence, seeing that the example chosen to support of a thesis is incorrect results in a downwards update on both the validity of the thesis and on its relevance. Likely low in magnitude in this case
Thanks for pointing out my imprecise statement there! What I meant of course “is we can’t prove the Collatz Conjecture” (which is a simple statement about a simple dynamic system), but I wrote something that doesn’t precisely say that, so apologies for that.
The main thing I intended to convey here is that the amounts of effort going into proving simple things (including the things you have mentioned that were in fact proven!) are often extremely unintuitively high to people not familiar with this, and that this happens all over CS and math.
I found Connor’s text very helpful and illuminating!
…But yeah, I agree about sloppy wording.
Instead of “you want to prove even minimal things about it” I think he should have said “you want to prove certain important things about it”. Or actually, he could have even said “you want to have an informed guess about certain important things about it”. Maybe a better example would be “it doesn’t contain a backdoor”—it’s trivial if you’re writing the code yourself, hard for a binary blob you find on the internet. Having access to someone else’s source code helps but is not foolproof, especially at scale, (e.g.).
Well, hmm, I guess it’s tautological that if you’re writing your own code, you can reliably not put backdoors in it. There’s no such thing as an “accidental backdoor”. If it’s accidental then you would call it a “security flaw” instead. But speaking of which, it’s also true that security flaws are much easier to detect or rule out if you’re writing the code yourself than if you find a binary blob on the internet.
Or the halting problem: it’s super-easy to write code that will definitely halt, but there are at least some binary blobs for which it is impossible in practice to know or even guess whether it will halt or not.
…Also, while we’re nitpicking, Connor wrote “175B FP numbers generated by unknown slop methods”. I would have instead said “175B FP numbers generated by gradient descent on internet text” or “175B FP numbers generated by a learning algorithm with no known security-related invariants” or something. (“Unknown” is false and “slop” seems to be just throwing shade (in this context).)
There is such thing as accidental backdoor: not properly escaping strings embeded in other strings, like SQL injection, or prompt injection
My impression is that if you walk of to a security researcher and say “hey what do you call the kind of thing where for example you’re not properly escaping strings embedded in other strings, like SQL injection?”, they probably wouldn’t say “oh that thing is called an accidental backdoor”, rather they would say “oh that thing is called a security vulnerability”.
(This is purely a terminology discussion, I’m sure we agree about how SQL injection works.)
I guess “backdoor” suggests access being exclusive to person who planted it, while “vulnerability” is something exploitable by everyone? Also, after thinking a bit more about it, I think you’re right that “backdoor” implies some intentionality, and perhaps accidental backdoor is an oxymoron.
And in particular, Collatz has been confirmed for all numbers up to 2^71. So if it turns up in a context of 64-bit integers, we know it holds.