1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ So, can we not see if two machines are equivalent from the configuration sequence for a specific input? $\endgroup$
    – Mary Star
    Jul 24, 2017 at 9:11
  • 1
    $\begingroup$ @MaryStar This theorem is equivalency for two TMs. However, you can evaluate the result of two machines for a specific finite string. $\endgroup$
    – OmG
    Jul 24, 2017 at 9:35
  • 1
    $\begingroup$ @MaryStar Ya, exactly. $\endgroup$
    – OmG
    Jul 24, 2017 at 9:40
  • 1
    $\begingroup$ @MaryStar for this specific example, you can't say they are equivalent. But, you should be aware, your example is based on a specific example. $\endgroup$
    – OmG
    Jul 24, 2017 at 10:08
  • 1
    $\begingroup$ @MaryStar Equivalence means that the two machines have the same output configuration (which includes final head position relative to the symbol string left on tape) for every possible input configuration. There is no such thing as 'equivalent for some input configurations'. AS long as there is at least one input-configuration for which the two machines leave a diferent output configuration, the two machines are not equivalent, period. And since there infinitely many possible input configurations, the only way to prove equivalence is through analysis. $\endgroup$
    – Bram28
    Jul 28, 2017 at 3:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .