2 ms·
>Moreover, it promises to produce equal results for equivalent programs, which would allow a solution of the halting problem, wouldn't it? I believe this is th
by wyager 12y ago
>Moreover, it promises to produce equal results for equivalent programs, which would allow a solution of the halting problem, wouldn't it?
I believe this is the case. So the article's promise (as I read it) can not hold true in the general case.
On a similar note, just write a program that runs the collatz conjecture and prints the result and a program that prints 1. Run them through Morte. If they compile to the same code, then boom, you've solved the Collatz conjecture :)
- tel 12y agoYou can't encode the Collatz Conjecture (in that way) in Morte. It would require an infinite amount of computation and infinite loops have been disallowed. You would have to get a little bit more creative with the dependently typed parts of CIC and then finding a program which matches the needed type is as of today an unsolved task.
- hawkice 12y agoEquivalent in the sense he's talking about means "I can take any declaration a = b and replace a with b in the scope of that definition". This is substantially weaker than "if the two programs produce the same output", which would obviously violate Rice's Theorem.