What is the definition of something being inherently sequential? Say we want to sum an entire array, I can certainly imagine some part of that as being sequential, but it's not clear just how much of it would be sequential.

For example, in this code snippet, each loop iteration is dependent on the previous, so in a sense it's all sequential:

int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; }

But the logic can certainly be parallelized by having n/2 threads doing an add over 2 elements, and then n/4 threads summing the results of the n/2 threads...etc, which yields an O(log(n)) number of sequential steps. Is this a tight bound? How would be prove it w.r.t the semantics of the program?

You're right. The way in which you have written this piece of code makes it inherently strictly sequential. This code in its current form is not parallelizable at all, so maximum speedup due to parallel execution = 1/S = 1, i.e., no speedup at all.

You're also right in saying that this code could be modified in a way to perform the computation in O(logn). In that case, the code will be partially parallelizable: statements like "i++" will still remain strictly sequential in nature.

Ah I see, my confusion was that I thought this law referred to the semantics of a program and not its actual instruction sequence, thanks for clearing this up!