What does it mean to be "independent of machine model"?

Question

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.

Answer 1

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.

Answer 2

You might want to look at the so-called Strong (or Efficient) Church-Turing Thesis (SCTT) - an informal statement that whatever can efficiently be computed by some natural device can efficiently be computed by Turing machines. Church-Turing Thesis (CTT) drops the efficiency requirement and states that whatever can be computed by some natural device can be computed by Turing machines.

Note: you can never prove such statements, but you could in principle disprove them by giving a computational model that people would deem natural that computes something (add "efficiently" for SCTT) that Turing machines don't. A word of caution: CTT is much older and much more universally believed than SCTT, because in the past 80 years people have given lots of (often very weird-looking) computational models that always turned out to be equivalent to Turing machines in terms of what they can compute (without efficiency requirement). In contrast, there is a lot of evidence that quantum computing is a serious challenge to SCTT.

See this link for some interesting discussion about SCTT.

Answer 3

other answers are nice, however how about a different angle, a fairly simple empirical answer? imagine this as an applied measurement problem. take any algorithm of interest that has some complexity, say a sorting algorithm with O(n log n) time. now run that algorithm on any computer, for increasing inputs, for a range the computer can handle, and graph the results, and observe that function. now go to any other computer, and repeat this exercise. claim: the graphs will be essentially the same and roughly differ only by a constant factor. so this justifies the use of Big-oh notation which is invariant/ equivalent under constant factors and definition of complexity classes (which are tightly coupled with each other).

in other words most major complexity classes in theoretical computer science can be regarded as machine independent! hence their study! they are "natural" mathematical objects that serve as basic algorithmic building blocks somewhat akin to prime numbers in this way.

this also relates to the P vs NP question. the two are not "yet" provably separated so in a sense there is no theoretical way to discriminate sub-P algorithms from each other through mathematical proofs (nobody can prove that any "typical" P algorithms are faster than each other, although there is an abstract proof based on the Time Hierarchy Theorem). in other words we can empirically measure algorithms and get upper bounds on them but since tight lower bounds are so difficult and impossible so far, the "granularity" of theoretical TCS cannot be finer so far. there is some new theory related to "fine grained complexity theory" that attempts to get a better "resolution".