3 ms·
"And I think those checks fall into the halting problem." Metaphorically, if you mean that there isn't going to be a concrete metric that really determines whe
by jerf 8y ago
"And I think those checks fall into the halting problem."
Metaphorically, if you mean that there isn't going to be a concrete metric that really determines whether two bits of text are "similar" with bright shining line, sure.
If you mean halting problem literally, no, this isn't affected by the halting problem. String similarity evaluation won't be strong enough to invoke the properties that result in a halting problem. For any two strings, you can certainly terminate in a reasonably period of time, and have the "correct" answer as defined by whatever the local meaning of "answer" is. (Barring a particularly perverse implementation of a string similarity algorithm probably explicitly constructed just to screw with my statement here, that for some reason starts executing the string as instructions directly or something.)