3 ms·
I wonder, while the halting problem is undecidable for arbitrary Turing machines, are there any practically useful subsets where the halting problem is decidabl
by xg15 7y ago
I wonder, while the halting problem is undecidable for arbitrary Turing machines, are there any practically useful subsets where the halting problem is decidable?
- lostmsu 7y agoThis is the best I could find: https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming There's also https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function implemented in https://en.wikipedia.org/wiki/LOOP_(programming_language) https://en.wikipedia.org/wiki/LOOP_(programming_language)
- caf 7y agoBPF (and eBPF) disallow all backwards jumps. This makes the halting problem trivially decidable (all programs halt in finite steps), and those programs are still practically useful in their problem domain.