5 ms·

> 3. They don’t understand what it means for something to be mathematically impossible. This one gets a lot of technically competent people. I spent a very un

> 3. They don’t understand what it means for something to be mathematically impossible. This one gets a lot of technically competent people. I spent a very unsatisfying 45 minutes vainly trying to explain to an eminent biologist that no, really, some statements really are _undecidable_ -- and no, that doesn't mean that at some future time we'll figure out a new approach that lets us decide them.

scott_s 7y ago
I encountered something similar almost a decade ago on this forum when discussing the halting problem: https://news.ycombinator.com/item?id=1322901 https://news.ycombinator.com/item?id=1322901
nikanj 7y ago
Reminds me of an infamous VC story I heard years ago: A bunch of engineers tell him that feature X is impossible due to latency, and the latency is capped by the speed of light. He challenges the team by asking them to speculate about options, if they managed to "disrupt" the industry by breaking that speed barrier, and gets mighty upset by these closed-minded engineers who are unwilling to accept any possibility of a breakthrough
- yummypaint 7y ago
  Thats when you say sure well start a basic research lab that will be $100 mil per year
- ahartmetz 7y ago
  It could possibly be a valid question: Think about what it would do for the customer, then see if there are different solutions for some of these things. But I guess that was not how it went.
- FakeComments 7y ago
  I’m not convinced the speed of light is a barrier when you can build a non-Euclidean quantum computer. Maybe the VC had a point, and the engineers were overly confident in one perspective — one that had assumptions subtly different from reality.
- copperx 7y ago
  Well, MOSH breaks through the speed of light latency limitation of SSH by ... predicting the server's response. Although the laws of physics can't be broken, in certain scenarios we can simulate we have done just that. And often that's just what you need to get ahead of your competition.
  - nikanj 7y ago
    You sound just like a VC! "You're saying we can't do HFT between Tokyo and New York faster than the speed of light? Here's a completely unrelated product, that does something completely different, and the limit they're working with doesn't really apply to us. So it is possible! Maybe you should go to Burning Man, that would open your mind.."
ahelwer 7y ago
There's a flipside of this, where people incorrectly lord "mathematical impossibility" over others as a way to shut down discussion. You see this on the topic of cryptographic backdoors especially. I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position. The interface between plain language and math is messy. I don't think I've ever seen something suggested that was actually mathematically impossible. Even the halting problem is easily solved in practice.
- xyzzyz 7y ago
  > I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position. I never seen anyone serious ever claim that cryptographic backdoors are impossible. > Even the halting problem is easily solved in practice. Like, how exactly?
  - ahelwer 7y ago
    If you're writing business logic in a modern programming language your code can almost certainly be proven to halt. Very few people are running around coding up the Collatz conjecture or feeding programs as input to themselves.
    - xyzzyz 7y ago
      It's clearly not true in any practical way. because most programs these days are huge beasts depending on stacks of millions of lines of code, so little can be conclusively proven about those. It's also wrong in theoretical sense, because what you're talking about is not "halting problem" at all.
      - tathougies 7y ago
        I think this really depends on how much you're willing to assume. You are right of course that the general problem is intractable, because you'd end up having to analyze frameworks, system calls, kernels, etc. But if you are able to assume those function as stated, then yes, you can certainly prove limited facts. For example, the sel4 microkernel is proven correct. Part of this proof of correctness is that all system calls do terminate. But, actually, the most straightforward way to show that most 'everyday' programs terminate is -- assuming functionality of the language runtime as stated -- that they typically consist of non-recursive functions or functions on structurally smaller inputs. It would be obnoxious, but not difficult to show that a program like 'grep' terminates, assuming functionality of the operating system and hardware on which its running. This is actually fairly straightforwards, and many many functional languages with a focus on correctness have totality checking builtin. For example, Idris and Agda. Of course, if you're going to ask to prove both functionality of the operating system (like Linux + glibc) or the processor itself, then that could indeed be trickier. But, if you limit your stack, it's certainly possible. The truth is that most computing does not consist of solving Turing complete problems.

scott_s 7y ago

I encountered something similar almost a decade ago on this forum when discussing the halting problem: https://news.ycombinator.com/item?id=1322901 https://news.ycombinator.com/item?id=1322901

nikanj 7y ago

Reminds me of an infamous VC story I heard years ago: A bunch of engineers tell him that feature X is impossible due to latency, and the latency is capped by the speed of light. He challenges the team by asking them to speculate about options, if they managed to "disrupt" the industry by breaking that speed barrier, and gets mighty upset by these closed-minded engineers who are unwilling to accept any possibility of a breakthrough

yummypaint 7y ago
Thats when you say sure well start a basic research lab that will be $100 mil per year
ahartmetz 7y ago
It could possibly be a valid question: Think about what it would do for the customer, then see if there are different solutions for some of these things. But I guess that was not how it went.
FakeComments 7y ago
I’m not convinced the speed of light is a barrier when you can build a non-Euclidean quantum computer. Maybe the VC had a point, and the engineers were overly confident in one perspective — one that had assumptions subtly different from reality.
copperx 7y ago
Well, MOSH breaks through the speed of light latency limitation of SSH by ... predicting the server's response. Although the laws of physics can't be broken, in certain scenarios we can simulate we have done just that. And often that's just what you need to get ahead of your competition.
- nikanj 7y ago
  You sound just like a VC! "You're saying we can't do HFT between Tokyo and New York faster than the speed of light? Here's a completely unrelated product, that does something completely different, and the limit they're working with doesn't really apply to us. So it is possible! Maybe you should go to Burning Man, that would open your mind.."

ahelwer 7y ago

There's a flipside of this, where people incorrectly lord "mathematical impossibility" over others as a way to shut down discussion. You see this on the topic of cryptographic backdoors especially. I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position. The interface between plain language and math is messy. I don't think I've ever seen something suggested that was actually mathematically impossible. Even the halting problem is easily solved in practice.

xyzzyz 7y ago
> I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position. I never seen anyone serious ever claim that cryptographic backdoors are impossible. > Even the halting problem is easily solved in practice. Like, how exactly?
- ahelwer 7y ago
  If you're writing business logic in a modern programming language your code can almost certainly be proven to halt. Very few people are running around coding up the Collatz conjecture or feeding programs as input to themselves.
  - xyzzyz 7y ago
    It's clearly not true in any practical way. because most programs these days are huge beasts depending on stacks of millions of lines of code, so little can be conclusively proven about those. It's also wrong in theoretical sense, because what you're talking about is not "halting problem" at all.
    - tathougies 7y ago
      I think this really depends on how much you're willing to assume. You are right of course that the general problem is intractable, because you'd end up having to analyze frameworks, system calls, kernels, etc. But if you are able to assume those function as stated, then yes, you can certainly prove limited facts. For example, the sel4 microkernel is proven correct. Part of this proof of correctness is that all system calls do terminate. But, actually, the most straightforward way to show that most 'everyday' programs terminate is -- assuming functionality of the language runtime as stated -- that they typically consist of non-recursive functions or functions on structurally smaller inputs. It would be obnoxious, but not difficult to show that a program like 'grep' terminates, assuming functionality of the operating system and hardware on which its running. This is actually fairly straightforwards, and many many functional languages with a focus on correctness have totality checking builtin. For example, Idris and Agda. Of course, if you're going to ask to prove both functionality of the operating system (like Linux + glibc) or the processor itself, then that could indeed be trickier. But, if you limit your stack, it's certainly possible. The truth is that most computing does not consist of solving Turing complete problems.