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.

Comeaux

Check this question #2551388 – Tuesday

I think this belongs on cstheory.stackexchange.com – Blotch

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.

Fraction

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.

Killebrew

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?

Conklin

If you show you can simulate a turing machine in your model, you are showing only one implication (your model is more powerful than turing machines), the other implication needed for the equivalence (turing machines can simulate your model) may be wrong but the church-turing thesis conjectures that the second implication is always true. – Afield