you are viewing a single comment's thread
view the rest of the comments
[–] 0 points 1 year ago* (last edited 1 year ago) (8 children)

The thing that always bothered me about the Halting Problem is that the proof of it is so thoroughly convoluted and easy to fix (simply add the ability to return “undecidable”) that it seems wanky to try applying it as part of a proof for any kind of real world problem.

(Edit: jfc, fuck me for trying to introduce any kind of technical discussion in a pile-on thread. I wasn’t even trying to cheerlead for LLMs, I just wanted to talk about comp sci)

  • source
  • hideshow 8 child comments
  • [–] 5 points 1 year ago (2 children)

    How do you know something is truly undecidable and not deterministically solvable with more computation?

  • source
  • parent
  • hideshow 2 child comments
  • [–] -1 points 1 year ago* (last edited 1 year ago) (1 child)

    Mathematically you might be able to prove I don’t always (and I’m not convinced of that even; I don’t think there is an inherent contradiction like the one used for the proof of Halting), but the bar for acceptable false positives is sufficiently low and the scenario is such an edge case of an edge case of an edge case, that anyone trying to use the whole principle to argue anything about real-world applications is grasping at straws.

  • source
  • parent
  • hideshow 1 child comment
  • [–] 1 point 1 year ago

    I suggest you re-read through the proof of the halting problem, and consider precisely what it's saying. It really has been mathematically proven.

    But fair enough, the program made in the halting problem you probably wouldn't ever encounter. But the consequence is, if you were trying to write an algorithm that solves the halting problem, you would have to sacrifice some level of correctness - and technically any algorithm you write would fail or loop forever on an infinite number of programs, surely one of them would be useful. Consider the Collatz conjecture. I severely doubt anyone would be able to "decide" the collatz conjecture program halting without it being a very specific proof of it (with maybe some generalisations).

  • source
  • parent
  • [–] 1 point 1 year ago (3 children)

    How would token prediction machine arrive at undecidable? I mean would you just add a percentage threshold? Static or calculated? How would you calculate it?

    (Why jfc? Because two people downvoted you? Dood, grow some.)

  • source
  • parent
  • hideshow 3 child comments
  • [–] 1 point 1 year ago (2 children)

    It’s easy to be dismissive because you’re talking from the frame of reference of current LLMs. The article is positing a universal truth about all possible technological advances in future LLMs.

  • source
  • parent
  • hideshow 2 child comments
  • [–] 1 point 1 year ago* (1 child)

    Then I'm confused what is your point on Halting Problem vis-a-vis hallucinations being un-mitigable qualities of LLMs? Did I misunderstood you proposed "return undecided (somehow magically, bypassing Halting Problem)" to be the solution?

  • source
  • parent
  • hideshow 1 child comment
  • [–] 1 point 1 year ago

    First, there’s no “somehow magically” about it, the entire logic of the halting problem’s proof relies on being able to set up a contradiction. I’ll agree that returning undecidable doesn’t solve the problem as stated because the problem as stated only allows two responses.

    My wider point is that the Halting problem as stated is a purely academic one that’s unlikely to ever cause a problem in any real world scenario. Indeed, the ability to say “I don’t know” to unsolvable questions is a hot topic of ongoing LLM research.

  • source
  • parent