3 ms·
IIRC 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
by stevetrewick 11y ago
IIRC 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.