The beauty of computability and complexity theory is that it's actually robust across models of computation. That is, while we analyze a Turing machine, the act

The beauty of computability and complexity theory is that it's actually robust across models of computation. That is, while we analyze a Turing machine, the actual machine is rather arbitrary. Paraphrasing from Sipser[1], the class of decidable and undecideable languages is the same for any "reasonable" model of computation where "reasonable" involves some basic things like not being able to do an infinite amount of work in a single step. So while any particular model (e.g. a Turing machine) is arbitrary, the class of languages is actually natural. [1]: http://www-math.mit.edu/~sipser/book.html http://www-math.mit.edu/~sipser/book.html This makes sense--any model of computation containing a countable number of instances will not be able to decide or even recognize every language. It also makes sense that these models would be able to recognize the same set of languages. I think this also holds for complexity classes. That is, the complexity of a language in a class like P or NP is the same across different models as long as those models are all deterministic or non-deterministic. So really, complexity theory is not about a man-made thing: it's about a deeper, fundamental truth. It's really awesome.