Hi Emily,
Thank you for a well-written and thought-provoking essay. You present an excellent analysis of the problem of a purely predictive physics within the orthodox conceptual model of physics. Your examples (references [37, 38]) are very telling. Both cases "prove" that what nature does (or likely does) cannot be algorithmically decided in finite time. You offer two potential resolutions.
1) Physical reality may be limited to a subset of possibilities--I believe Tim Palmer explores this idea in his essay.
2) The universe has infinite time, and nature acts globally across time.
In my essay I explore a third possibility. Any proof is based on assumptions, and I suggest that the orthodox conceptual model of physics, on which the proofs in [37 and 38] are based, is lacking. Specifically, it rejects entropy and dissipation as fundamental properties of physics. As described in my essay, this is strictly a matter of interpretation of observations; this conclusion is not empirically based on observations. In thermodynamics, entropy is a fundamental measure of the relative stability of state, but in statistical mechanics, it is a measure of an observer's incomplete information and the observer's subjective description of the system's disorder.
With no fundamental definition of stability, it is impossible for an algorithm to select one possibility or another. The orthodox interpretations of physics have no irreducible "values" by which it can assign relative stabilities to different alternatives.
In my essay, I reference an essay ([13]) in which I define a measure of relative stabilities for alternative processes of dissipation. Referring back to your reference [37], this measure of stability would easily allow an algorithm (and nature herself) to decide which of different allowable emission spectra would (most likely) result as a quantum system transitions to a lower energy state. This third possibility interprets physical reality as objective, local, causal, and fully compatible with quantum observations, but with irreducibly random and irreversible transitions in state.
Harrison Crecraft