If you wrote a correct binary search algorithm and you observed that, under one language implementation, the time complexity scaled linearly with the size of the input instead of logarithmically, you would think the semantics of the program were changed.

If you used an in-place sort algorithm and observed memory requirements that scale super-linearly with the size of the input, you would think the semantics of the program were changed.

In languages with such tail call guarantees, tail recursion _is_ a loop. It semantically encodes constant space complexity.