I like to dream about problems that have not given rise to any convincing formal theory because they exist so far beyond our current grasp, no one knows what solving them might even look like.
In particular, there is a whole class of such problems that has proven equally enticing and inscrutable ever since people failed to make anything much of it in the Golden Sixties. Its least confused definition is negative: let us call it anti-reductionism. For my purposes, reductionism is about understanding a phenomenon by talking about things in some sense smaller than it (internal structures, individual properties...). By contrast, anti-reductionism explains an object by talking about things larger than it.
Take meaning. A book holds no meaning in itself. There is exactly nothing in its particles or their arrangement that contains the Little Prince or the Bhagavad Gita in an intrinsic and necessary way. Given two appropriate encoding schemes, you could represent both of those stories by the same configuration of atoms, sounds, neural impulses, or raindrops on a fig tree at dawn. With the appropriate decoding process, you could read the Talmud from the position of the stars in the sky. Now, if you had a blackbox decoder that actually took the trajectory of Betelgeuse and converted it into bits of the Talmud, you might be forgiven for thinking that the content of the Talmud was held in the decoder rather than in the stars. But you use your brain to decode what the decoder says; was the meaning of the Talmud in your brain all along?
Meaning is not a signal. It is not in the signal, nor in the channel, the encoder or the decoder, the sender or the receiver. It is in the entanglement of all these things, in the ways they all move together. The Little Prince is a property of the union of the book and its readers, their language and mind and society, that is not found in any of them separately. (I know that sounds mystical, but bear with me for a moment; I do not use the word "entanglement" lightly here)
This is why information theory, being a reductionist approach, has nothing to say about meaning, or even about information in the usual sense. It is (very self-consciously) about information capacity: things like "you cannot summarize Hamlet in a haiku without losing something". In other words, it is concerned with potential, not actual information - how much there could be at most, not what is indeed there. This potential meaning is indeed a property of the atoms of a book, a property of the signal and the channel, something you can investigate in isolation. Not so for actual meaning.
Now, consciousness certainly has something to do with meaning. Why, then, are we trying to look for consciousness in the states - mental or physical - of an object? By the same reasoning, we might be able to gauge its potential consciousness, but its actual consciousness is not contained in itself. It is a property of its entanglement with its surroundings.
(At this point, people tend to cheat by making claims about reflexivity, i.e. consciousness being its own surroundings, but this is really Russell's paradox in camo pants: the self on which reflexivity operates is not the self that performs the operation, but a higher order object, typically the long list of past selves, and consciousness gives the current self a role in that stream.)
Likewise, intelligence, artificial or otherwise, hides in the entanglement of the problem-solver with the problem, being absent from either alone. And my point extends to purpose (or function), which may sound like a theoretical bogeyman to some biologists, but is obviously a very concrete notion in engineering, design or strategy. Potential function exists in an electronic component or a move in chess; actual function only in the component's position in a whole circuit, or the move's role in a whole game.
To clarify: purpose is not present in a component's relations to other components, staying at the same level of organization, but in its relation to the level above. Complex systems approaches (network science, systems biology...) get that wrong - they have extended reduction, which uses level N-1 to explain level N, in a way that, at best, explains level N by itself (e.g. nodes by their links). They are still lacking a true reference to level N+1.
These approaches cannot describe actual function, but they have come to realize that there exist containers of potential functions, what grammarians call a nature. Noun is a nature, and it is a property of an object in isolation. Subject is a function and exists only within the context of a larger object, proposition or sentence. As is well known, there exist many-to-many mappings between natures and functions, of the potential-actual sort: for instance, nouns have the potential to be subjects, contrary to inflected verbs.
Confusingly enough, functional ecology and functional genomics are both about natures, not functions. A predator, a feedback loop, a memory are all natures, "whats". By contrast, actual function is about "why". Common wisdom notwithstanding, "whys" are entirely welcome in science: they are naturally answered in anti-reductive terms, by describing an object on the basis of something larger than it, something that includes the object partially or totally. (1)
We are very good at formalizing the other sort of knowledge, the one that captures structures by describing their parts, that understands an object from things smaller than it, contained in it.
But if you reduce the description to the object and to its parts, then any meaning, consciousness, strategy, purpose should vanish without trace (though one can still see the empty space where they could have been, the potential for them to arise). Hence, we need theories that proceed by anti-reduction - or, if you pardon the jargon, non-mereological knowledge.
Now, how can there be two different ways of describing the same objects? If we had infinite processing power and precision, we could certainly reconstruct the infinitely large from the infinitely small, or understand the infinitely small by its role in the infinitely large, and the two forms of knowledge might perfectly coincide. In a world of finite means, however, it seems likely that some objects will be best understood one way, other objects the other way - and yet other objects may be available only to yet other modes of understanding.
There is no guarantee that everything that can be understood by anti-reduction could equivalently be reconstructed by reduction without infinite means - that there is a bottom-up algorithm that halts, or whatever else is your metaphor for how knowledge proceeds. This is nothing new: deterministic chaos is also a statement about the limitations of a mode of description (mechanics) that is, in principle, perfectly consistent and causally complete. It points to the fact that one has to look at a different set of observables to form a description that is simpler than the thing it describes, and scientifically operational.
There is also no guarantee that anti-reduction is both useful in itself, and usefully formalized. Usefulness can be argued from the abundance of deeply anti-reductive intuitions in almost every qualitative science. However, when it comes to the possibility of formalizing it, there is very little evidence for or against. Older attempts - von Bertalanffy's general system theory and the like - rapidly abandoned the problem of analyzing natural systems in favor of designing artificial ones (2). And recently renewed interest in those concepts (systems biology, systems thinking...) has simply led to a different sort of reduction, inspired and powered by these artificial systems.
Nowadays, vocal anti-reductionism is mostly found in pseudoscience, or in the handwaviest of science, when it is not a catchy rebranding of confused reductionism. But I believe that this failure is a mere historical accident, and in no way a sign that there is truly no good research to be done here. The one science that could never be anything but anti-reductionist is grammar, and as such, I am quite inclined to present it as the model to follow and expand. Some day, I might even try to argue that the human ability to understand phenomena by anti-reduction comes from repurposing our hardwired cognitive module for grammar (if one is willing to believe, with Chomsky, that such a thing exists) while reduction is intrinsically visual-spatial.
(1) When I talk about understanding an object from something larger than it, this does not mean the usual mathematical idea of belonging to a set or class. What matters is not whether the object is part of something, but how the object relates to what it is part of. If there is only one such relation, "X is a member of Y", then there is no functional distinction. And indeed, set membership is often equated to assigning a property to the object itself (being red equals belonging to the set of red objects), which is a reductionist action.
(2) With some success, see for instance cybernetics and computer architecture.