3 ms·

I am 100% sure that parent poster was being sarcastic at the hype around LLMs and how many think they can solve everything, even if said thing is impossible to

• mythhabit 3y ago
  There is some nuances here. While the general halting problem for a general Turing machine is undecidable, and with a fairly easy to understand proof as well, the computers we run today are not a general Turing machine. They are of a weaker class called Linear Bounded Automatons and for the programs they can run, the halting problem is fact decidable, on a theoretical level due to their finite nature. So we will probably never practically solve the halting for LBAs, but the quest for this AGI that should be able to solve this, is not just day dreaming, it's rooted in the theory.
  • kaba0 3y ago
    I have to admit my knowledge of complexity theory doesn’t extend too far, but isn’t the solution to LBAs just.. brute forcing? Also, is it even decidable a priori whether a program is LBA vs requiring a tape that is not only linear function of its input?
    • vidarh 3y ago
      The worst case solution is just brute forcing, yes. An LBA is effectively "just" a Turing machine that has a finite tape. A typical current computer is an LBA only if you disallow all IO of any sort or bound that IO and include it as part of the system you analyse and so fix the values which will be provided as IO, which of course is a very unusual situation, and so that constraint does not really make the halting problem more tractable in situations we usually care about.
    • mythhabit 3y ago
      The naive way of deciding it it halts is executing it and keep track of all state between steps. If the machine halts, you're done, if it repeats a state, it's looping. If you can represent a program with an LBA, it is by definition a context sensitive language and decidable. You could also show it by making a equivalent gramma for the language, that accepts the same input as the program. This gramma must be constructed in a certain way, and then you know it is a context sensitive language.
  • vidarh 3y ago
    A machine we have to today in isolation with no form of IO are not general Turing machines, but almost all of them do have that and so if you consider them in isolation rather than the full system (which would include all sources of inputs) the halting problem applies. E.g. code to the effect of "while gets() {}" will either halt or not halt depending on the input, but which isn't decidable without knowing or constraining that input. We can certainly look for AGI that can do better at deciding the halting of decidable programs, but even for current computers the general halting problem is undecidable without adding artificial constraints.
    • mythhabit 3y ago
      IO is just state and can be represented on the tape. You can construct a machine for every conceivable input at every time during the execution and reason about them.
      • vidarh 3y ago
        "while (gets()) {}" is undecidable because the "tape" is conceptually infinite. So, no, you can not construct a machine for every conceivable input without imposing an artificial constraint on the input size. Put another way: For every tape you construct and analyse, there is a tape one segment longer that might contain a symbol that can alter the outcome.
        • mythhabit 3y ago
          You can, theoretically, keep constructing machines for every input you need. Yes you are bounded, but you can say "this machine will halt for every input it can receive in the next 100 years", because you need to quantify the input in blocks of time.
  • odyssey7 3y ago
    It’s fun to think about. What about the Collatz conjecture? If we run it for arbitrary n, on a computer that represents numbers up to n_max, we could know if it will halt within n_max steps. Since only n_max numbers are representable, we could track all visited numbers to detect any cycle that might occur. If on the other hand any iteration would exceed n_max, then the program would halt by crashing. hailstone :: Integer -> Integer hailstone n | n `mod` 2 == 0 = n `div` 2 | otherwise = 3 * n + 1 collatz :: Integer -> Bool collatz n | hailstone n == 1 = True | otherwise = collatz (hailstone n) Edit: however, you would need enough disk space to store the cycle-detection index.
    • kaba0 3y ago
      We have actually done something like that up to the 32bit n_max for sure (but maybe even 64bit?), without any number that would contradict the conjecture. But yeah, it is not even trivial to say whether it has a bounded max memory, so in case of an arbitrary precision int type, it may not be LBA, but Turing?
      • odyssey7 3y ago
        I guess I was thinking about indexing the visited numbers from a graph-traversal-algorithm-interview perspective instead of a CS theory one. We can actually do it in O(1) space complexity in exchange for higher time complexity. For i in range 1..n, compute n_i, the ith number in the hailstone iteration, and then continue the hailstone iteration n_(i+1)..n_max to see if n_i is equal to any of them. This takes us to quadratic time complexity, O(n * n_max), or constant complexity depending on how you look at it, but it only requires storing a single n_i at a time for cycle detection. But then again, if you actually loop for n_max iterations without halting by reaching 1 or crashing, then you had to reuse a number somewhere, so the explicit cycle detection isn’t really important.
• treprinum 3y ago
  Halting problem is one of the problems that arise from precise mathematical definition and its outskirts. LLMs are all about making sense from unstructured text, i.e. lying on the opposite end of the spectrum where math has no direct way to do anything. So while the poster was sarcastic, they also missed the mark.
  • kaba0 3y ago
    The halting theory is analogous to Gödel’s incompleteness theorems and these are fundamental truths to any system. That matrix multiplication that deep learning does is hardly immune to that.
    • treprinum 3y ago
      They are fundamental truths to systems based on certain assumptions we are taking for granted, e.g. binary logic (and not e.g. quantum logic), Turing-like computing model etc. Not that deep learning has anything to do with those, but it excels in human-like properties where simple formula-derived math descriptions fail all the time.
      • kaba0 3y ago
        Is a NN a computable function? Yes, as we calculate them on Turing machines. Then it is prone to every limitation of computable functions. Humans are also limited by the Turing model’s limits, we can only ever determine computable functions as well. With all due respect, it is stupid to assign more capabilities to ML than what we know is fundamentally the limit..
        • treprinum 3y ago
          While that's true, halting problem is completely useless in the real world (nobody designs user-facing apps while thinking about whether the program halts), whereas picking data from speech is a much more useful one that was long unreachable for "clean" closed-formula math.
• kybernetikos 3y ago
  The halting problem is absolutely solvable in some cases, it's just the general case in which it is unsolvable. If LLMs were able to decode web pages and executables in a high proportion of the interesting cases, that would already be extremely useful. Humans can't do this in the general case either, but we still hire them to do jobs like this.
  • kaba0 3y ago
    > If LLMs were able to decode web pages and executables in a high proportion of the interesting cases Why would it be extremely useful?
• thanatropism 3y ago
  I remember the hype around XGBoost and Kaggle contests asking to solve problems in prime number theory.