6 ms·
Turing kicked us out of heaven
- orionblastar 3y agoI remember using a while loop as part of a Password program in Pascal. On an Apple 2 it would cause a stack overflow and force the user to reboot if the password was wrong three times.
- Turskarama 3y agoThese days you have to pay extra for security features like that.
- pwdisswordfishc 3y ago> First, write a bash script P1 that runs a SAT solver on every possible SAT problem and halts if any of them take exponential time. You don't actually have to run P1, just call HALTS(P1, Solver) to see if the solver solves all problems in polynomial time. That's not recursively enumerable, that's Π₂. And ABC conjecture looks even harder.
- ccppurcell 3y agoTo add to this for the author and other readers: SAT restricted to an individual instance is always constant time.
- veave 3y ago[flagged]
- lieuwex 3y agoWhy is that?
- bheadmaster 3y ago[flagged]
- rowbin 3y ago> [...] because computers aren't Turing machines and have finite memory, so all programs are guaranteed to halt That's just wrong. `while true {}` never halts even with finite memory.
- tommica 3y agoI guess the heat death of the universe will stop that at least
- compressedgas 3y agoThat won't stop a suitably advanced computer. (You know the story of The Last Question.)
- mcv 3y agoEventually the computer will have to reboot to install updates.
- bheadmaster 3y agoI assume they meant "all programs are provably halting or non-halting". Which, by the way, isn't true if you take into account the fact that a computer may interface with an external, potentially infinite, memory device - such as a memory tape reader-writer, together with a human who responds to the "INSERT NEXT TAPE TO CONTINUE" messages by going out to the store and buying more tape. The whole "acktshually computer is just a finite state machine" is the most annoying "gotcha!" I've ever heard from computer scientists. There's a reason we invented virtual memory and file systems - it's so we can treat real computers like Turing Machines, and increase the memory when needed without having to re-write our whole systems every time.
- rowbin 3y agoI'm sure they ment that. It's also enough to have a program fetch truely random data from random.org.
- 3y ago
- bionhoward 3y agoThe amount of cursed acceptance of this idiotic proof is incredible. It’s like saying you’re not allowed to flip coins because they might land on their head. The whole argument for the undecidablility of the halting problem is based on an anti symmetric G which cheats at the halting problem by invoking H, but when you make H, you could detect that and crash H. the halting problem is either truly solvable, or there is an actual proof which doesn’t rely on weak unconstructable paradox. At least TFA didn’t regurgitate the bad proof and accept it. However, they did worse, they accepted the bad proof without even attempting to regurgitate it.
- pringk02 3y agoTwo questions out of curiosity: * Do you also reject Church's more formal proof? * Do you more generally reject the rule of the excluded middle and would you generally think of yourself as a Constructivist?
- bheadmaster 3y ago> the halting problem is either truly solvable, or there is an actual proof which doesn’t rely on weak unconstructable paradox. Do you have any proof of this statement?
- gizmo686 3y ago"Crashing" is not a concept in Turing machines. More practically, if you does_halt algorithm "crashes" on certain inputs, then it fails to give an answer to those inputs, and so is not a solution to the halting problem. There is a real insight in your comment though. There is a weaker version of the halting problem, where the goal is to write a does_halt function that returns yes/no/maybe. That problem is trivially solvable. There are also non-trivial solutions to it that are actually useful.