# What does it mean to be “independent of machine model”?

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.

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.

• Thanks for the answer. You gave examples of machines which have native notions of "polynomial time" and all those notions agree. Say we want to formalize that as a theorem along these lines: For all decision problems $X$ and all encodings of $X$ as $X_A$ and $X_B$ for machines $A$ and $B$ which each have a notion of computation time, $A$ solves $X_A$ in polynomial time iff $B$ solves $X_B$ in polynomial time. Can such a theorem be rigorously stated and proved (after restricting the scope of "all encodings", "all machines with a notion of computation time", etc., to be as narrow as necessary)? – echinodermata Nov 20 '15 at 4:48
• @echinodermata You can come up with appropriate definitions to make this trivially true, but in truth machine independence is an informal observation. For example, quantum computers seem to invalidate this independence. – Yuval Filmus Nov 20 '15 at 8:02

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.

• This answer is misleading, since Turing machines can be polynomially smaller than RAM machines, for example. This is the advantage of $\mathsf{P}$ over linear or linearithmic time. – Yuval Filmus Nov 20 '15 at 19:55