Thank you very much for your comments!
Yes indeed, I've thought a lot about retrocausality. Basically, I think there are two different `types' of retrocausality - either you can have both a forward and backward arrow of time, or you can just have global laws (e.g. optimizing some constraint over the whole of history) which implies that what happens at one moment affects what happens at all other moments, past and future. I agree that the first type leads to contradictions of the type you mention, but I think the second type avoids that problem because the global equations will necessarily be solved in a consistent way.
Yes, I enjoyed Dr Hossenfelder's essay very much. It's a very interesting question to determine exactly which problems of pure maths translate over into physical reality - I'm sure there are many applications which we are yet to discover!
Hmmm, interesting - my intuition is that undecidable problems would become decidable if you allow yourself infinite time to solve them, but I'm not aware of any results one way or another on this question!