Re:Morte: an intermediate language for super-optimizing func...
by tel on Friday September 12, 2014 @01:32PM
(#8309255)
You 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.
Re:Morte: an intermediate language for super-optimizing func...
by hawkice on Friday September 12, 2014 @01:52PM
(#8309366)
Equivalent 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.
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 :)