4 ms·
Don't think so, doesn't computer program equivalence require solving the halting problem and undecidable problems? For example, consider the empty program, and
by henrydark 3y ago
Don't think so, doesn't computer program equivalence require solving the halting problem and undecidable problems?
For example, consider the empty program, and the program that print "hello, world!" if an undecidable condition is met. I think checking if these two programs are equivalent is undecidable
- maweki 3y agoFor these two programs it's easy to check that they are not equivalent. The magic words are "in general" and in general, program equivalence, as well as all other interesting program properties, are in general undecidable (Rice's Theorem).