patternMinor
What does it mean to be "independent of machine model"?
Viewed 0 times
whatindependentmeandoesmachinemodel
Problem
I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with subroutines or composition or something. My question is: What precisely does that mean? or, what precisely does it mean to be independent of the choice of machine model?
It makes sense to me that invariance under change of machine model - whatever that means - would make $\mathsf{P}$ a theoretically natural class to study, sort of the same way that Euclidean geometry is interested in the notions which are invariant under similarity, or linear algebra is interested in the notions which do not depend on a particular choice of basis. (The analogy is not entirely accurate, as those fields are only interested in such invariant notions, while computer science is still interested in properties of particular machine models.) While I understand what it means to be independent of the choice of basis, I don't understand what it means to be independent of the choice of machine model. Is there even a unique such concept, or are there several different concepts used in different contexts?
I've talked about $\mathsf{P}$ as a specific example, but what other commonly-studied ideas (in complexity theory or otherwise) are machine-independent in the same sense that $\mathsf{P}$ is? Are there ones that are not?
Thanks for helping to clear this up for me.
It makes sense to me that invariance under change of machine model - whatever that means - would make $\mathsf{P}$ a theoretically natural class to study, sort of the same way that Euclidean geometry is interested in the notions which are invariant under similarity, or linear algebra is interested in the notions which do not depend on a particular choice of basis. (The analogy is not entirely accurate, as those fields are only interested in such invariant notions, while computer science is still interested in properties of particular machine models.) While I understand what it means to be independent of the choice of basis, I don't understand what it means to be independent of the choice of machine model. Is there even a unique such concept, or are there several different concepts used in different contexts?
I've talked about $\mathsf{P}$ as a specific example, but what other commonly-studied ideas (in complexity theory or otherwise) are machine-independent in the same sense that $\mathsf{P}$ is? Are there ones that are not?
Thanks for helping to clear this up for me.
Solution
The class $\mathsf{P}$ is usually defined as the class of decision problems solvable in polynomial time by (one-tape) Turing machines. However, you get the same class if you replace "one-tape Turing machines" by "multi-tape Turing machines", "RAM machines", "machines running C natively", and many other machines. That's what is meant by the class being independent of the machine model.
Other classes, such as $\mathsf{TIME}(n)$, are very much dependent on the machine model: there are (I think) languages which can be computed in linear time on a two-tape Turing machine but not on a one-tape Turing machine.
The reason we are happy that $\mathsf{P}$ is machine-independent is that it makes $\mathsf{P}$ a very natural class. You don't have to ask yourself whether the correct model is Turing machines with one tape, two tapes, or more: all definitions result in the same class. The same cannot be said about $\mathsf{TIME}(n)$, for example.
Other classes, such as $\mathsf{TIME}(n)$, are very much dependent on the machine model: there are (I think) languages which can be computed in linear time on a two-tape Turing machine but not on a one-tape Turing machine.
The reason we are happy that $\mathsf{P}$ is machine-independent is that it makes $\mathsf{P}$ a very natural class. You don't have to ask yourself whether the correct model is Turing machines with one tape, two tapes, or more: all definitions result in the same class. The same cannot be said about $\mathsf{TIME}(n)$, for example.
Context
StackExchange Computer Science Q#49718, answer score: 5
Revisions (0)
No revisions yet.