3 ms·
>Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write. We could confirm this though! It's not like
by runT1ME 5y ago
>Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write.
We could confirm this though! It's not like we can't find out if a given program halts or is inconsisent. Godel talks about it in his letter to Von Nuemann.
- tsimionescu 5y agoThere are programs for which we can check this, but there is no general procedure to check if any program halts. Even ignoring the halting problem itself, say we analyze a program and realize it halts iff P=NP, or pi to the e is transcendental, .or if Pi's decimal expansion at position Graham's number is divisible by 3. Will that program halt? It might be very hard to say. More promisingly, there are ways to construct programs such they will halt, using total languages (though not every problem can be solved with such a limitation).
- runT1ME 5y agoWe can write a general procedure to see it any given program halts within n-steps however.