26 ms·
> To be pedantic (and why not), I don't think that the procedures described in the paper strictly qualify as algorithms because there's no guarantee of terminat
by JadeNB 11y ago
> To be pedantic (and why not), I don't think that the procedures described in the paper strictly qualify as algorithms because there's no guarantee of termination.
I don't think that's part of the description of 'algorithm' (although I don't know if the word has a technical definition, so that we may be left arguing about how we use the word personally). Otherwise, there could be no algorithm for listing all the natural numbers, for example.
- stevetrewick 11y agoIIRC the formal definition is something like (but probably not) : any finite set of steps that can be represented by a Turing (complete?) machine. I have seen definitions both with and without the requirement for a halting state. Fortunately someone will be along shortly to explain it properly.
- JadeNB 11y agoHowever, the existence of a halting state does not imply that all execution paths eventually reach it. Certainly I have never seen a definition (of an algorithm, rather than, say, a total language) that builds in that requirement; otherwise, what would be the objects considered in the halting problem? By this definition, they couldn't just be algorithms, or else "RETURN TRUE" would be a correct decision procedure.