By non-trivial algorithm, I mean anything besides the trivial "do nothing" algorithm that simply terminates.

This is pretty trivial, but don't algorithms require a notion of monotonic time?

From what I understand, all computation requires a sort of reduction step, from the reduction of the transition function in Turing machines to the types of reduction within lambda calculus. But having reduction requires a notion of change itself means that a change of state must be defined with respect to a change in some constant unit of change that is uniform.

Whether that notion of change is the steady rate of change of the instruction count register of a computer or the steps in the reduction of a formula to normal form, does every single type of computation require a notion of change, and, therefore, "time" as a sort of immutable, constant, and uni-directional measure of change?

  • $\begingroup$ Using non-homogenic multi"processor" systems, this seems something to keep an eye on. (I don't think I follow require a notion of change, and, therefore, "time" as a sort of … measure of change.) $\endgroup$ – greybeard Oct 16 '16 at 16:55
  • $\begingroup$ @greybeard Basically, to describe a change in state, we need time, right? $\endgroup$ – CinchBlue Oct 16 '16 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.