How to tell if a machine is Turing machine equivalent

Question

I found a Wikipedia article of a list of Turing machine equivalents. However, it doesn't tell a method of how to determine whether a given machine is Turing machine equivalent.

Do I need to use the definition of a Turing machine to prove it? Could you give an example?

Thanks.

Answer 1

The standard way of proving something turing complete is to implement one of the TM-equivalents in your machine. If that is possible to do, then your machine is turing-complete. If it's not, then it's not. So if I was trying to prove, say, that a new programming language is turing complete, I'd pick the TM-equivalent that's simplest to implement, and then show that my programming language can simulate it.

Answer 2

Actually it cannot be really proven. At least, fully formalizing these common equality proofs might require much more formal logic than to be expected even in theoretical computer science. ( if you disagree, tell me! I am eager to discuss about this. )

However, it is mostly clear from context. You try build a simulation of a "machine" of scheme of computation A within another such model of computation B. This means B can simulate A, and hence has the full power of A. If you do vice versa, these two models are called equivalent.

Answer 3

Of the top of my head: If your machine can simulate one of the known Turing machine equivalent machines, then your machine is also Turing machine equivalent.

Probably the easiest way to go about doint something like this.

EDIT: I am not implying that this is a requirement for a machine to be Turing machine equivalent, alltough it might be. Maybe somebody that is a bit more skilled in theoretical informatics can clear me up on this?