Is there any data structure that can't be represented or described inside a computer?
There is a systematic way of computing datatype representations of mathematical objects: anything that can be described in higher-order intuitionistic logic has a representation as a datatype. Because we are talking about descriptions, and not about proofs of theorems, it does not even matter much that the logic is intuitionistic and not classical. Pretty much any mathematical object you encounter in practice can be represented. Some examples that can be done easily: real numbers, the space of square-integrable measurable functions $L^2[0,1]$ and other infinite-dimensional Hilbert spaces, Banach spaces, the space of compact subspaces of $\mathbb{R}^n$, etc.

Roughly, the process goes as follows. Take you favorite model of computation and build a realizability topos from it. Then take your description of the mathematical object and interpret it in the topos. It will tell you how to represent data, because the topos is built in such a way that every object is equipped with a data representation, and every statement is witnessed by a program. In most cases we do not actually need the entire topos, the much smaller and easier subcategory of modest sets suffices.

There is an important caveat: in intuitionistic logic an object may have several inequivalent descriptions which are classically equivalent. These will lead to different data representations (and this is good, as it means we can express more computational distinctions).

The process of interpretation is automatic. To make that point, Chris Stone and I wrote a tool rz which does this. You can feed it the definition of real numbers, or an infinitely dimensional Banach space, or anything like that, and it spits out a specification. (The software experienced bitrot, I should update it, but the paper has many examples.)

Let me also address the common misconception that "non-computable objects cannot be represented in a computer". There is a difference between non-computable and non-representable. For example, the digits of a real number may be written down on the tape of a Turing machine. It doesn't matter whether the real number in question is computable, it can be stored on the tape. The question of "who stored it onto the tape" is a separate concern. You may object that the tape is not infinite. Actually, it is infinite in most textbooks. But people like to press this point, to which I have two responses.

First, we may replace the infinite tape with a potentially infinite tape, i.e., think of the real number as a process which emits digits on demand. This can be some sort of a physical process, say a quantum-mechanics experiment that produces bits by making measurements. Would anyone like to presuppose that the real number so obtained is computable? In this case they have to produce some evidence for such a claim. Good luck with that. The moral here is that it is largely irrelevant whether "all reals in this universe are computable". What is important is that we can represent whatever reals there are, and that would by definition be all of them.

Second, we can study models of computation that have no infinite components, for example the $\lambda$-calculus. In such models infinite data, say a real number, is represented by a program that produces the data, say the digits of the real number. So obviously only computable reals may be represented. But this doesn't matter! The corresponding realizability topos still thinks there are uncountably many reals, and is a self-consistent world of mathematics.

For further explanation on how to represent uncountable data, I refer to my blog post Representations of uncomputable and uncountable sets. It's a bit of a rant, actually.

The takeaway is the motto from my PhD thesis:


  Data are continuous, programs are computable.