Quite right! However, all we have are (imperfect?) versions of a Turing machine to solve the folding problem!

Maybe a Lisp machine would do better ;-)

At the end of the day, a linear sequence of amino acids has to end up in a three-dimensional conformation with short-range contacts being formed between atoms far away in the primary (linear) sequence. Add to this the complexity from long-range effects critical for the final structural stability and biological/biochemical function.

And don't even get me started on Intrinsically Disordered Proteins -- where, frankly, the future of the entire field lies !!!