4
$\begingroup$

See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case.

EDIT

If it can be reduced to Halting problem, then how?

EDIT 2

@Ariel's answer doesn't satisfy me since given the concrete machine $T$ and input $x$ he states that there exists a computable function that is equal to $1$ everywhere except $x$ and indicates whether $T$ terminates on $x$, on $x$. Note: there is no algorithm for building such a function since it would answer the Halting problem immediately. He proceeds with noting that if that function coincides (by required in the question decision algorithm) with the constant $1$ (as a function) then $T$ terminates on $x$. Otherwise - it does not. So, Halting problem solved, a contradiction. Except there is no. We didn't build an algorithm for building that function ($f_{M_x}$, if I understood correctly), so we didn't build an algorithm for deciding whether arbitrary $T$ terminates on given $x$. @Ariel, correct me, if I'm wrong...

EDIT 3 @Ariel was correct!!! Since I did not mentioned that required decider algorithm must only accept not descriptions of computable functions but Turing machines implementing them, his answer was fully correct. Now the thing - I just require for seeked algorithm to process only pairs of always halting Turing machines and testing them for equality on every input. @Ariel, I'm really sorry :-(

EDIT 4 And if somebody still wishes to answer this question, Rice's theorem for partial functions does not help, since I don't require the decider beeing searched for to be such over all partial function, only over total function, i.e. it may not halt on arbitrary not-always-halting Turing machine.

$\endgroup$
  • 1
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Aug 29 '15 at 10:14
  • $\begingroup$ I was pretty sure it can be reduced to the Halting problem and I would say it for undecidability it needs for the arbitrary partial function needs to be separated to the two total ones such that if they give the same output then the given algorithm diverges and otherwise terminates (or vice versa). But I could not find the principle of such a separation. $\endgroup$ – Andrew Zabavnikov Aug 29 '15 at 11:19
  • $\begingroup$ By the way, what is a computable function? I mean, is it enough really to encode one somehow to define it? If true, what formal ways to encode it there are which do not define it's computation algorithm? $\endgroup$ – Andrew Zabavnikov Aug 30 '15 at 18:01
  • $\begingroup$ A function is computable if there exists a Turing machine (one way to define them) that for all input $x$ halts with output $f(x)$. Defining a function does not have anything to do with it's computability. For example, $f(M,x)=1 $ iff $M$ halts on $x$. I defined it (say, using a first order logic formula), but did not present an algorithm for computation (as you know, it does not even exist). $\endgroup$ – Ariel Aug 30 '15 at 19:16
8
$\begingroup$

The problem

Do two halting Turing machines accept the same language (or compute the same "function")?

is undecidable.

Let $M$ be an arbitrary Turing machine. Let $M'$ be a Turing machine that on input $x$, simulates $M$ (on some predefined input) for $|x|$ steps and accepts if (and only if) $M$ halts within $|x|$ steps (or, if you want to go with a TM computing a function, returns $1$ if $M$ halts within $|x|$ steps and $0$ otherwise).

If $M$ doesn't halt then $M'$ accepts the empty language (or, computes the function $f(x)=0$). If $M$ does halt then the language $M'$ accepts is non-empty (or, the function is non-constant).

This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether $M'$ is equal to the machine accepting the empty language (or, the machine computing the function $f(x)=0$).

This avoids all the issues of the function not being total or being unable to construct the function explicitly.

$\endgroup$
  • 1
    $\begingroup$ Thanks! That is brilliantly simple and elegant, as it seems to me! :-) $\endgroup$ – Andrew Zabavnikov Aug 30 '15 at 10:54
4
$\begingroup$

Representing computable functions as Turing machines, the language your interested in is $\left\{ \left( \langle M_1\rangle,\langle M_2\rangle \right)| L(M_1)=L(M_2) \right\}$. As everyone here mentioned it is undecidable. A simple example for a reduction from the halting problem would be $\left(\langle M \rangle,x\right)\rightarrow \left(\langle M_x \rangle,\langle M_{\Sigma^*} \rangle \right)$, where $M_x$ is the machine accepting all inputs different than $x$, and on $x$ simulates $M$, if $M$ halts $M_x$ accepts. $M_{\Sigma^*}$ is a machine that accepts all inputs. It is easy to see why this is a reduction from the halting problem to your desired language.

As Giulia Frascaria mentioned, this problem might be decidable for weaker models (e.g. finite automata).

Edit: To avoid long discussion in the comments ill add it here. For any Turing machine $M$, it's characteristic function $f_M(x)=1\iff x\in L(M)$ is total, If $M$ does not halt on $x$ then $x\notin L(M)$ and $f_M(x)=0$. Why, in this case the function $f_{M_x}=1 \iff x\in L(M_x)$ is computable? Look at two machines: they accept all inputs other then $x$, while one of them accepts $x$ and the other doesn't. Clearly one of these machines computes $f_{M_x}$, this argument isn't constructive, i didn't build the machine computing $f_{M_x}$, but iv'e shown it exists.

Edit 2: Think about what would a valid reduction between the halting problem and the problem you stated should look. Given a pair $\left(\langle M \rangle,x\right)$ i need to describe two total computable functions that agree on all inputs iff $M$ halts on $x$. By describe, i mean i should only have a way to encode them (do not confuse with the term computing or anything else). I have described $f_{M_x}$ in terms of $M$ and $x$. It is a well defined total function. Specifically, it outputs $1$ on all inputs other than $x$, and on $x$ outputs 1 iff $M$ halts on $x$. I did not say the machine $M_x$ computes it, i simply encoded(described) it using $M$ and $x$. Then i claimed that the function $f_{M_x}$ is also computable. So given a pair $\left(\langle M \rangle,x\right)$ i was able to output a pair of functions (and by outputing a function, i do not mean outputing the machine computing it, only outputing some description of that function) which agree on all inputs iff $M$ halts on $x$.

$\endgroup$
  • $\begingroup$ I think M_x is not supposed to be total. So is your argument erroneous? $\endgroup$ – Andrew Zabavnikov Aug 29 '15 at 18:12
  • $\begingroup$ Think about $M_x$ as it's characteristic function, i.e. $f(x)=1 \iff x\in L(M_x)$. So you are in fact comparing two total functions (if $M_x$ does not halt on $x$, then you simply have $f_{M_x}(x)=0)$. $\endgroup$ – Ariel Aug 29 '15 at 18:17
  • $\begingroup$ Okay. Now I will ask what I should have asked long before: what is $L(M_x)$? $\endgroup$ – Andrew Zabavnikov Aug 29 '15 at 19:12
  • $\begingroup$ Is then $f(x)$ computable? $\endgroup$ – Andrew Zabavnikov Aug 29 '15 at 19:19
  • $\begingroup$ $L(M_x)=\left\{ y\in \Sigma^* | M_x(y) =1 \right\}$, the set of all strings on which $M_x$ halts and outputs 1. And yes, $f_{M_x}$ is computable. Why? well, lets look at two turing machines: both accept all input other than $x$, and one accepts $x$ while the other doesn't. They both halt for all inputs, and obviously, one of them computes $f$, hence it is computable. Notice that my argument wasn't constructive, i didn't build the machine which computes $f$, but it obviously exists. $\endgroup$ – Ariel Aug 29 '15 at 19:27
2
$\begingroup$

I would say that in general it is undecidable: in fact, this problem can be reduced to the Halting problem, which states that it is not decidable whether a given turing machine (read "function") terminates on an input x.

This does not mean that you can't find a solution to specific given problems. For example, if it is possible to write these two functions as finite state automata, it is then decidable whether they generate the same language (or output).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.