3 ms·
Isn't this basically the halting problem?
by jandrese 9y ago
Isn't this basically the halting problem?
- progval 9y agoAlmost. Its answer is a direct consequence of Rice's theorem (“A Turing machine can't decide non-trivial properties on Turing machines given as input”), which is itself proven using the undecidability of the Halting Problem (“A Turing Machine can't decide whether Turing Machines given as input stop.”).
- LolWolf 9y agoSure, two partial functions are equivalent over a set d iff they halt on the same subset of inputs and have equal outputs whenever each terminates. Then, if you could decide equality of two functions, f, g, over a finite domain d, then let g be a function that loops infinitely for any input, and check equality of f and g over a singleton containing some input. If f doesn't halt, then they're equal (since they both don't halt over the same set) and if f halts then they're not equal since the sets they halt on don't agree.
- deleted 9y ago[deleted]