3 ms·
I think it's impossible, or close to it. Isn't it just another form of the halting problem? https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.o
by oblio 7y ago
I think it's impossible, or close to it. Isn't it just another form of the halting problem? https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- sp332 7y agoI'm not sure it's relevant. All real machines have limitations that we accept when we write programs and feed them data. Anyway just because you can't prove that all possible programs will or won't run correctly doesn't mean you can't prove this for a useful subset of programs.
- striking 7y agoWell, the alternative is that you limit the set of things you can do, such that you no longer have a Turing machine. But that's certainly less fun, isn't it?
- AnimalMuppet 7y agoDepends on your definition of fun.
- robto 7y agoThe halting problem states that it's impossible to know if computation will terminate in the general case, but there are lots of specific cases where we can prove that it will terminate. The Idris language compiler (think haskell with dependent types) will actually warn/error if you've written a function that it can't prove will terminate. It's actually really cool! If you're interested in learning more, I'd check out any talks by Edwin Brady or pick up his book[0] [0]Type-Driven Development with Idris