4 ms·
Because the number of operations in a sort is bounded. You can perform any sorting algorithm without turning completeness because you don't need the while loop
by cdancette 9y ago
Because the number of operations in a sort is bounded. You can perform any sorting algorithm without turning completeness because you don't need the while loop basically.
- pron 9y agoThis applies to virtually any algorithm with a known bound. Any such algorithm can be carried out by primitive recursive functions. However, contrary to folklore, this makes absolutely no difference in verification complexity (see my other comment https://news.ycombinator.com/item?id=16383436 https://news.ycombinator.com/item?id=16383436). This can be easily shown by noting that we can assume -- with no loss of generality -- that any program is primitive recursive by implicitly adding a counter to each and every loop/recursive call, that counts down from, say, 2^500, and halts the program if it ever reaches zero (in fact, this is much more limited than primitive recursive as we're happy with a constant bound). As the counter will never reach zero in our physical universe, there is no change in program semantics, and therefore we can assume that all programs are written in non-Turing-complete languages if that were to help us in any way. Alas, as my other comment shows, it doesn't in the least.