I disagree with your characterization. Of course, true protein folding computation is hard (literally NP-hard I believe) but the halting problem can be proven to be uncomputable, whereas protein folding is clearly computable - every time a protein is produced in our cells, protein folding is computed. Practically, the two may be the same, in the sense that we can neither truly compute how a complex amino acid sequence will fold nor whether a complex computer program will halt, but one is merely intractable, whereas the other is impossible.
Not true. Protein folding is just as incomputable as the halting problem. Read up on chaperone proteins. They manipulate the protein as it folds to change the final structure.
Producing a list of biologically common folds of a protein sequence without access to the actual environment they see is directly analogous to producing a list of all reachable statements in a program over all possible inputs.
Biological processes are analogous to running a program once on a well tested input.
Prion-based diseases are like fuzz or pen testing the folding process.
Hmm, computability is more of a mathematical formalism thing. Physical phenomena aren’t really at question; computability is trivial. But yeah, protein folding in silico is pretty tough.
