patternMinor
What does actually reasonable mean when we say "reasonable model of computation"?
Viewed 0 times
whatcomputationmeansayreasonableactuallydoeswhenmodel
Problem
I have seen in many text when the author says "reasonable model of computation". What does it really mean?
Solution
In computational complexity theory, Peter van Emde Boas formulated the Invariance Thesis saying that:
'Reasonable’ models of computation can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.
See eg Cambridge Encyclopedia of Philosophy.
Reading this thesis as a definition, one can call a reasonable model of computation a model of computation that is equipped with a time complexity measure which is polynomially equivalent to counting steps on a Turing machine (ignoring space complexity for the moment).
I have used the term in this sense in my own work here.
'Reasonable’ models of computation can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.
See eg Cambridge Encyclopedia of Philosophy.
Reading this thesis as a definition, one can call a reasonable model of computation a model of computation that is equipped with a time complexity measure which is polynomially equivalent to counting steps on a Turing machine (ignoring space complexity for the moment).
I have used the term in this sense in my own work here.
Context
StackExchange Computer Science Q#50144, answer score: 3
Revisions (0)
No revisions yet.