4 ms·

> “LLMs will look at any .exe and be able to integrate with it immediately”. The LLM will look at any .exe and determine if it halts.

KronisLV 3y ago
> The LLM will look at any .exe and determine if it halts. At that point you'd need an AGI that can figure out something we can't. Edit: but yeah, sarcasm. Nowadays I can't even tell sometimes.
- wruza 3y ago
  I believe it was a positive sarcasm in gp.
- kaba0 3y ago
  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 do, e.g. the halting problem. Do note that the halting problem is fundamentally true, no AGI will realize some new way around, unless are mathematics are flawed to the core.
  - 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.
- reichstein 3y ago
  I think KronisLV's point, presented ironically, is that not even an AI superior to human reasoning, which can figure out things we cannot, can decide the undecidable. Being undecidable is a hard limit, not something that requires better algorithms. Another phrasing of it could be: No finite program can decide it. (And what even is an infinite program? Not something we can run on any current computer.) If an AI is itself a finite-sized program, something we run on computers, it cannot possibly solve the halting problem. And _any_ non-trivial property of programs is undecidable, so an AI "integrating with any .exe file" isn't really meaningful. It's just words.
  - vidarh 3y ago
    > Another phrasing of it could be: No finite program can decide it. (And what even is an infinite program? Not something we can run on any current computer.) The complexity of the program trying to decide is not really the issue. An "infinite program" could add an infinite number of extra rules to try to cut down on the time taken to determine if a decidable program halts, but the issue with the halting problem is that there is an infinite set of undecidable programs where the size of your detector will make no difference to your ability to decide them. E.g. "while next_symbol() == some_arbitrary_symbol {}" is undecidable unless you add constraints on the length or contents of the input. Even if you haven infinite-sized program you can't decide whether or not the unconstrained version of that halts, because deciding it is equivalent to being able to determine if an infinite tape contains a given symbol, and no matter how long you scan the tape the symbol can always be the next one on the tape after the last symbol you scan. > And _any_ non-trivial property of programs is undecidable I don't think I agree with this without adding the qualifier "in general". There are a whole lot of useful properties we can decide, but often the properties will have constraints. E.g. for a whole lot of programs where we can't decide whether or not they will halt, we can still decide whether or not they will halt assuming certain properties of their inputs. E.g. we can decide the property of my pseudo-code above that it will halt IF "some_arbitrary_symbol" is in the input. We can also decide the property that whether or not it will halt in general is undecidable, and that is itself useful to know, because for many programs knowing what makes them undecidable is useful in order to suggest e.g. adding timeouts, or ensuring there are ways to bail early from certain actions without restarting the machine or killing the program. For a whole lot of problems we also do not really care whether or not a given property is decidable. We care whether they're decidable often enough within certain time constraints, and that's a very different ballgame.
abwizz 3y ago
i suspect this is because they can divide by zero
chromoblob 3y ago
.exe's (for the usual architectures) run on finite-state machines, not Turing machines. So, indeed, that is possible. If the .exe connects to a service that runs on something more powerful than finite-state machine, though, I don't know.
- kaba0 3y ago
  That’s still a stupid pedantry, and is even false. A Turing machine only makes use of at most n cells of its tape after n steps - so running it for a finite number of steps is possible even in finite memory. Especially that modern computers can do arbitrary side effects, having access to the whole universe as tape, which is still finite, but so is time. There is no way to differentiate between a magical Turing machine with infinite tape and a “fake” one that has n-sized memory under any program that takes n steps, so for all practical purposes they are identical.
  - chromoblob 3y ago
    Why are they identical? A program may use more steps than memory.
    - kaba0 3y ago
      A Turing machine can either go left or right on its tape (some versions have a stay step as well, doesn’t matter). If all your program does is step right forever, than it will use the maximum amount of memory, but only ever a finite amount, that is equal to the number of steps taken. So if you don’t have infinite time (you don’t have), and you have big enough memory for the particular use case so that you don’t get OOMKiller involved, then you have a Turing machine for all complexity theoretical and practical purposes, especially that RAM is not analogous to the Turing machine tape - your computer has much more state than only its memory, if it has network access, you can basically make use of a cloud vendors whole army of servers as storage, just as an example.
      - deleted 3y ago
        [deleted]

KronisLV 3y ago

> The LLM will look at any .exe and determine if it halts. At that point you'd need an AGI that can figure out something we can't. Edit: but yeah, sarcasm. Nowadays I can't even tell sometimes.

wruza 3y ago
I believe it was a positive sarcasm in gp.
kaba0 3y ago
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 do, e.g. the halting problem. Do note that the halting problem is fundamentally true, no AGI will realize some new way around, unless are mathematics are flawed to the core.
- 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.
reichstein 3y ago
I think KronisLV's point, presented ironically, is that not even an AI superior to human reasoning, which can figure out things we cannot, can decide the undecidable. Being undecidable is a hard limit, not something that requires better algorithms. Another phrasing of it could be: No finite program can decide it. (And what even is an infinite program? Not something we can run on any current computer.) If an AI is itself a finite-sized program, something we run on computers, it cannot possibly solve the halting problem. And _any_ non-trivial property of programs is undecidable, so an AI "integrating with any .exe file" isn't really meaningful. It's just words.
- vidarh 3y ago
  > Another phrasing of it could be: No finite program can decide it. (And what even is an infinite program? Not something we can run on any current computer.) The complexity of the program trying to decide is not really the issue. An "infinite program" could add an infinite number of extra rules to try to cut down on the time taken to determine if a decidable program halts, but the issue with the halting problem is that there is an infinite set of undecidable programs where the size of your detector will make no difference to your ability to decide them. E.g. "while next_symbol() == some_arbitrary_symbol {}" is undecidable unless you add constraints on the length or contents of the input. Even if you haven infinite-sized program you can't decide whether or not the unconstrained version of that halts, because deciding it is equivalent to being able to determine if an infinite tape contains a given symbol, and no matter how long you scan the tape the symbol can always be the next one on the tape after the last symbol you scan. > And _any_ non-trivial property of programs is undecidable I don't think I agree with this without adding the qualifier "in general". There are a whole lot of useful properties we can decide, but often the properties will have constraints. E.g. for a whole lot of programs where we can't decide whether or not they will halt, we can still decide whether or not they will halt assuming certain properties of their inputs. E.g. we can decide the property of my pseudo-code above that it will halt IF "some_arbitrary_symbol" is in the input. We can also decide the property that whether or not it will halt in general is undecidable, and that is itself useful to know, because for many programs knowing what makes them undecidable is useful in order to suggest e.g. adding timeouts, or ensuring there are ways to bail early from certain actions without restarting the machine or killing the program. For a whole lot of problems we also do not really care whether or not a given property is decidable. We care whether they're decidable often enough within certain time constraints, and that's a very different ballgame.

abwizz 3y ago

i suspect this is because they can divide by zero

chromoblob 3y ago

.exe's (for the usual architectures) run on finite-state machines, not Turing machines. So, indeed, that is possible. If the .exe connects to a service that runs on something more powerful than finite-state machine, though, I don't know.

kaba0 3y ago
That’s still a stupid pedantry, and is even false. A Turing machine only makes use of at most n cells of its tape after n steps - so running it for a finite number of steps is possible even in finite memory. Especially that modern computers can do arbitrary side effects, having access to the whole universe as tape, which is still finite, but so is time. There is no way to differentiate between a magical Turing machine with infinite tape and a “fake” one that has n-sized memory under any program that takes n steps, so for all practical purposes they are identical.
- chromoblob 3y ago
  Why are they identical? A program may use more steps than memory.
  - kaba0 3y ago
    A Turing machine can either go left or right on its tape (some versions have a stay step as well, doesn’t matter). If all your program does is step right forever, than it will use the maximum amount of memory, but only ever a finite amount, that is equal to the number of steps taken. So if you don’t have infinite time (you don’t have), and you have big enough memory for the particular use case so that you don’t get OOMKiller involved, then you have a Turing machine for all complexity theoretical and practical purposes, especially that RAM is not analogous to the Turing machine tape - your computer has much more state than only its memory, if it has network access, you can basically make use of a cloud vendors whole army of servers as storage, just as an example.
    - deleted 3y ago
      [deleted]