Skip to main content
2 of 5
Added Wikipedia link.
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

It's not tautological at all.

A model of computation is Turing-complete if

  1. it can simulate all Turing machines (it is at least as powerful as Turing machines);
  2. it can be simulated by Turing machines (it is no more powerful than Turing machines).

One thing that Turing machines can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can't do at least one thing that Turing machines can't do, so it fails part 1 of the definition, so it isn't Turing complete. There's no circularity because we didn't define Turing-completeness in terms of itself: we said that Turing-completeness is the property of being able to do exactly the same things as Turing machines.

But there are plenty of other things that models of computation might fail to do. For example, deterministic finite automata can't recognize the class of strings consisting of some number of $a$s followed by the same number of $b$s. Turing machines, on the other hand, can recognize that class of strings.

Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?

I'm not sure what you mean by "define the capabilities of Turing machines". The capabilities are defined in terms of the finite state automaton operating on the infinite tape. (I'll not repeat the full definition but you can find it, e.g., on Wikipedia.)

David Richerby
  • 82.2k
  • 26
  • 144
  • 238