4 ms·
> [...] 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
by 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.
- rowbin 3y ago`while fetchRandomInt() != 0 {}`
- bheadmaster 3y agoBut that would diverge away from the definition of a Turing Machine.
- marcosdumay 3y agoAll programs are guaranteed to either halt or repeat their state. There is no guarantee they will halt.
- rowbin 3y agoYes, every program will either halt or not halt. Some programs are guaranteed to halt (`int main() {return 0;}`) some are guaranteed to not halt (root comment). Some are undecidable (at least with infinite memory, with finite memory they are still undecidable in practice, because computing whether they halt or not would take until well after the heat death of the universe)