Let's start with some comments. You say:
I'm putting this question here and not in computer science or math because the incomputability of Komlogorov Complexity and the validity of the Curry-Howard Correspondence are settled fact.
Nothing wrong with questions that ask after philosophy of math, computer science, and physics, especially if they are cross-domain questions. This is the right forum.
One can view the job of scientists as to develop the simplest possible axiomatic system that is consistent with all prior observations. For example, in celestial mechanics, one might consider the Ptolemeic system where each planet revolves around the earth, but there are cycles in those cycles (see illustration), and cycles in those cycles in those cycles, etc. up to hundreds of cycles on cycles. In principle, a theory like this can be consistent with all prior observations, but it asks us to assume a huge number of parameters as axioms...
Epicycles are a famous example from the history of science that recognizes that parsimony is one criterion for choosing among theories when observation leads to underdetermination. A simpler example is underdetermination in linear regression where our observation is a simple set of points.
Are there other views on what science is that don't reduce it to a data compression problem?
Absolutely. One is free to abstract science to the deductive-nomological method or Ramsey sentences and examine them with the tools of mathematical logic or information theory, but obviously the sciences, which use a methodological naturalism including inference to best explanation which when used tightly coupled with philosophical methods (an epistemological flavor known as naturalized epistemology (SEP)) often promote particular philosophical worldviews like physicalism or property dualism. The sciences contribute knowledge to society, broadly, that is applied to solve problems and make predictions. (And I say sciences on account of Popper's problem of demarcation.) And they are a source of cultural inspiration such as works of science fiction. There is far richer understanding in the philosophy of science and the sociology of science than metrics and formal language models.
Can you recommend a text on the philosophy of science that is approachable by non-philosophers?
If you have no texts, then a really quick overview is Introduction to Philosophy of Science by Oxford Press written by Samir Okasha (GB). It's shallow, but it does highlight some important points. My favorite is an out-of-print edition of Blackwell's A Companion to the Philosophy of Science edited by Newton-Smith (GB) which is not the same as their The Blackwell Guide to the Philosophy of Science. The Companion has a series of essays based on terminological topics, all of which were edited with the strategy of integrating them into each other. Other sources include the Stanford Encyclopedia of Philosophy and the Internet Encyclopedia of Philosophy both of which are online and free. There are other's like Encyclopedia of Philosophy and Routlidge's Encyclopedia.
There are primary sources, like works by the logical positivists, history of science texts. Kuhn's The Structure of Scientific Revolution, Hempel's Aspect of Scientific Experience, and Popper's various works that are informative. And Google books has a whole selection of introduction to philosophy of science texts to numerous to recite.
Does the incomputability of kolmogorov complexity imply that we will never have a final theory of everything?
Well, and lastly we get to what Carnap hated about philosophical questions: meaningless terminology that constituted fodder for metaphysical speculation that had no bearing in observation or the reduction of language to the physical world in the way of concrete objects and operational definition. 'Theory of Everything'. If you take ToE to be the typical physical understanding, then what's best to say is that it is quite possible that we may integrate quantum mechanics and relativity, supplant the standard particle model.
Alternatively, if you approach it from a sociological angle, perhaps as a scientific constructivist, a theory of everything might encompass not only a unified model of the fundamental forces (gravity HAS to be quantified! ; ) but also the develop of the philosophy of science itself with 100 more years of research. In such a view, the theory would be a social edifice of language that facilitates practice, and can't be reduced to anything less than the observations of all people everywhere. Maybe something like Asimov had in mind in his foundation trilogy with psychohistory.
But, if you're thinking there's going to be a limited set of axioms that generate all solutions and predictions and completely explains everything in the universe, then that's an entirely different perspective on theory of everything. Then giving all of the theorems about epistemological incompleteness and non-determinism, it doesn't seem likely.
In any case, you are now a fully initiated member of this site when you get the boilerplate response: "depends on what you mean by the 'theory of everything'". Once you build up the vocabulary in the domain of discourse, you'll know because you'll be able read Wilfrid Sellars, John McDowell, Ian Hacking, Bastiaan van Fraassen, and other's and not be entirely lost.