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, 2016 at 16:55
  • $\begingroup$ @greybeard Basically, to describe a change in state, we need time, right? $\endgroup$
    – CinchBlue
    Oct 16, 2016 at 17:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.