[Math] Equivalent Turing machines

Question

I have written the configuration sequence for $4$ Turing machines. Now I want to check which of the Turing machines are equivalent and which are not.

Are two turing machines equivalent when they do the same at an entered word? For example if both reverse the a's and b's and the c's remain constant and both halt at the same place maybe at the empty space before the string or the one after that?

Or is there an other way to check the equivalence?

Answer 1

Generally, As mentioned here:

equivalence of two Turing machines is undecidable.

So, you have no algorithm to decide this (see here):

There is no algorithm that takes as input two lambda expressions and outputs TRUE or FALSE depending on whether or not the two expressions are equivalent. This was historically the first problem for which undecidability could be proven. As is common for a proof of undecidability, the proof shows that no computable function can decide the equivalence. Church's thesis is then invoked to show that no algorithm can do so.

Church's proof first reduces the problem to determining whether a given lambda expression has a normal form. A normal form is an equivalent expression that cannot be reduced any further under the rules imposed by the form. Then he assumes that this predicate is computable, and can hence be expressed in lambda calculus. Building on earlier work by Kleene and constructing a Gödel numbering for lambda expressions, he constructs a lambda expression e that closely follows the proof of Gödel's first incompleteness theorem. If e is applied to its own Gödel number, a contradiction results.

Anyhow, to show two TMs are equivalent, you must simulate the transition of $M_1$ with $M_2$ and vice versa.