I kind of feel like the specification would call for an idealized lock free queue. Whereas the code would generate a good enough approximation of one that can be run on real hardware.

To invert your polynomial analogy, the specification might call for a sine wave, your code will generate a Taylor series approximation that is computable.

A thorough specification might even include the acceptable precision on the sine wave; a thorough engineer might ask the author what the acceptable precision is if it's omitted.