Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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).