3 ms·
No, it has been proven that there exists no turing machine that can solve the halting problem. If we assume that there exists a computable f(N) that is always g
by KalMann 1y ago
No, it has been proven that there exists no turing machine that can solve the halting problem. If we assume that there exists a computable f(N) that is always greater than BB(N) then we can construct a Turing machine that solves the halting problem. Therefore no computable f(N) can exist.
- _alternator_ 1y agoThis was the key missing part for me; the program can’t exist, whether we can prove it is beside the point. Thanks.
- KalMann 1y agoI think the issue is related to notion of a "direct" proof vs "proof by contradiction". What I gave was a proof by contradiction. Once you start thinking about the philosophy of proofs it, it's an interesting question to ask whether or not proofs by contradiction should really count. I don't know much about this but you can search up the term "Law of the excluded middle" is a good place to start reading about these concepts.
- _alternator_ 1y agoTrust me, I understand proof by contradiction :). The point I was missing was the difference between an undecidable question vs impossible. See the rest of the thread above.