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.EDITIf 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 4And 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.
Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?
turing machines;undecidability
The problemDo 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.