5 ms·

Stack limits exist because of the halting problem. If we knew in advance which thread would need extra contiguous memory for deep recursion using variables of a

• ndsipa_pomu 3y ago
  > We should just solve the halting problem That might be a little bit like "draw the rest of the damn owl" and besides, wouldn't that destroy our encryption schemes?
  • explaininjs 3y ago
    It’s a joke, it’s mathematically unsolvable. Though even if it were I don’t see the connection to encryption?
    • ndsipa_pomu 3y ago
      Sorry if I got wooshed. It's currently unsolved, but I don't think that it's been proved to be unsolvable as surely that would prove P ≠ NP. The connection to encryption is that integer factorisation could then be solved in polynomial time which would break current systems, though in theory a much longer key length could be used to try to outpace computer power, especially if the polynomial algorithm is hugely inefficient. Edit: I see that the halting problem has indeed been proved to be unsolvable and it doesn't imply P ≠ NP
      • explaininjs 3y ago
        P/NP and Halting are entirely different concepts. I suggest reading up on the Halting problem - it’s actually very mind opening. Edit: it wouldn’t be a stretch to call it the most important result in all of mathematics
        • ndsipa_pomu 3y ago
          If you have a solution to the halting problem, then it would be possible to cast the P/NP problems in terms of a program and knowing whether or not it halts would allow you to determine whether P=NP.
          • explaininjs 3y ago
            That may be, but statements that start “if false …” aren’t very useful.
          • sharkbot 3y ago
            The halting problem has been proven definitively undecidable via proof by contradiction, by Alan Turing. The proof implicitly created the notion of Turing machines, a key model of computation. There is a solution to the halting problem. It’s that it is undecidable.
        • dreamcompiler 3y ago
          Yes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.
          • explaininjs 3y ago
            I had originally written something to that effect, but recanted after I saw Turing claimed “what I shall prove is quite different from the well-known results of Gödel”. I’d need to sit down longer to determine how equivalent they really are.
            • dreamcompiler 3y ago
              Would love to see the reference for this. I expect he might be referring to the idea of executing an embodied algorithm on a machine, while Gödel was talking about pure math.
              • 3y ago
      • tsimionescu 3y ago
        The halting problem (writing an algorithm which can take any other algorithm and an initial condition and return true/false for whether it halts or not) has nothing to do with P or NP. Even if all algorithms were solvable in O(n), the halting problem would still be unsolvable.
  • bregma 3y ago
    It's humour because the "halting problem" has a simple and elegant proof that it is impossible to solve in the general case. TFA's request for general computing to use unlimited stack operation for every thread of execution is equivalent to a call for the halting problem to be provably possible in O(1) time. It's the unexpected juxtaposition of these two oppositional ideas that provides the basis for humour. Of course, if it has to be explained it loses its funny.
• addaon 3y ago
  > If we knew in advance which thread would need extra contiguous memory for deep recursion using variables of automatic storage duration we could allocates its stack at an address with enough space left. And this is a real option. While determining the maximum stack size of an arbitrary program is halting-problem-equivalent (requires determining the maximum depth of the runtime call graph), we can trivially choose to write code where determining the maximum stack size is also trivial. This static analysis is commonly done on embedded systems, and essentially comes down to "don't write code that you can't guarantee the correctness of", which should be starting stakes anyhow.