Problem Detail: 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.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45683
Related
