this post was submitted on 02 Oct 2023
1147 points (98.6% liked)
Programmer Humor
19589 readers
589 users here now
Welcome to Programmer Humor!
This is a place where you can post jokes, memes, humor, etc. related to programming!
For sharing awful code theres also Programming Horror.
Rules
- Keep content in english
- No advertisements
- Posts must be related to programming or programmer topics
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Just because it's not possible on a Turing Machine doesn't mean it's impossible on a PC with finite memory. You just have to track all the memory that is available to the algorithm and once you detect a state you've seen already, you know it's not halting ever. The detection algorithm will need an insane amount of memory though.
Edit: think about the amount of memory that would need. It's crazy but theoretically possible. In real world use cases only if the algorithm you're watching has access to a tiny amount of memory.