Fully general machine translation is almost trivially undecidable.
You can have a sentence that's ambiguous in one language, but that can't have that ambiguity (e.g. gender) in the target language, and the resolution of the ambiguity can depend on the truth value of an arbitrary sentence.
