4
$\begingroup$

We all know that, at least theoretically, there are several possible models of computation, varying in structure.

Strictly speaking, there are several (not just one) models of computation that exist or have been implemented in real life. Some machines (for example, amplifier circuits), though inexact, can be considered analog computers, but that's not what we commonly think of as 'computers', is it?

The machines that we usually think of as 'computers' are implementations of a computation model with discrete parts (discrete memory slots, discrete instructions and clock cycles, etc.) I've always wondered if there's some form of data that can't be represented/stored inside these discrete structures.

I've brought up this question in many websites, but I usually only find people who approach this issue with an incomplete picture of the problem, and without the required logical rigor.

I've been told that nothing with a continuous structure can be stored inside a computer, but from what I've gathered, this is not always true. Take the example of a circle (a geometrical shape). It's true that it has an infinite number of points in its circumference, but I can't say that they represent an infinite amount of information, since they can be derived from a very small number of parameters (center and radius) and a bunch of simple laws (algebra and symbolic math). My intuition tells me that this is the case for any geometrical shape, unless it has an infinite number of parameters, in which case I don't really know what to think.

Is my intuition accurate? Is this the case for any structure with a finite number of parameters? Are Von-Neumann/Harvard/... computers unfit to store certain data structure(s)? Has this been mathematically proven? Is the proof constructive? Are there any data structures that can't be stored in any known model of computation (or, for that matter, any model of computation)?

Note: I'm asking all of this from intuition. Even though I write code for a living, and harbor a great interest in Computer Science (and have a little knowledge of it through self-study), I am not a CS or Math graduate. From my limited, newbie perspective, I would think that this question belongs to the Theoretical Computer Science Stack Exchange, but I genuinely don't know if it's too basic, so I'll just play it safe for now.

$\endgroup$
  • $\begingroup$ If I'm understanding you correctly, you ask if we can describe a structure that cannot be represented by any structure on a computer. Then how can I give you this description on a website running on a computer, if judging from your circle example, any description that uniquely defines the structure will do? $\endgroup$ – Discrete lizard Jan 29 '18 at 18:58
  • 5
    $\begingroup$ I'm not really sure what you're asking. Isn't a data structure representable essentially by definition? Sure, there are plenty of examples of data that can't be represented in a computer (e.g., any uncomputable set). However, to me, a "data structure" is an arrangement of data within a computer's memory. Such a thing is represented in a computer by definition. $\endgroup$ – David Richerby Jan 29 '18 at 19:00
  • $\begingroup$ @Discretelizard, yeah, I used the word "represent", but I think the word "describe" would be closer to what I'm trying to ask. To answer your question: "Then how can I give you this description on a website running on a computer, if judging from your circle example, any description that uniquely defines the structure will do?" I don't know. I guess you could describe it by referencing constructs that are known to humans, but that live outside of the computer world. $\endgroup$ – Lehonti Jan 29 '18 at 20:28
  • $\begingroup$ @DavidRicherby you said "to me, a 'data structure' is an arrangement of data within a computer's memory." What I am asking is if there is any data that can't be arranged within a computer's memory. $\endgroup$ – Lehonti Jan 29 '18 at 20:34
  • 1
    $\begingroup$ I don't think there is a difference between 'cannot be described' and 'cannot be described on/by a computer'. I think that therefore this question ultimately boils down to either 1. Do there exist machines (or even natural phenomena) which cannot be described? or 2. Do there exists 'theoretical models' that cannot be described? 1 seems to be a question of metaphysics and 2 of meta-mathematics. I think that this question has more to do with philosophy than computer science. $\endgroup$ – Discrete lizard Jan 30 '18 at 14:09
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A very important property of representations is equivalence, asking whether two objects represented by $A$ and $B$ are the same. For most sufficiently complicated mathematical objects asking $A = B$ is computationally infeasible, but if we had infinite time it'd still be fine. However my intuition says that for plenty of formal systems asking $A = B$ is uncomputable or even independent of whatever axioms you assume. Does the system you suggest suffer from this? If yes, I'm not sure if I agree that anything is representable as (IMO) being able to ask $A = B$ is a must have property. Still +1. $\endgroup$ – orlp Jan 31 '18 at 13:32
  • $\begingroup$ I think it would be worthwhile to stress the 'tagline' from your post here in this answer: "It is meaningless to discuss representations of a set by a datatype without also considering operations that we want to perform on the set.". This directly addresses the vagueness associated with the question in 'representing or describing' structures and IMO is an important aspect when formalizing those notions. In particular, this justifies the focus of representations on computers as opposed to a piece of paper. $\endgroup$ – Discrete lizard Jan 31 '18 at 13:43
  • $\begingroup$ While you are referencing concepts that are unknown to me, I have to thank you because this is the kind of answer I'm looking for. Are there any books you recommend for studying the mathematical constructs you mentioned? $\endgroup$ – Lehonti Jan 31 '18 at 15:32
  • $\begingroup$ @Lehonti: an introductory textbook that does not require much knowledge of logic or realizability is Klaus Weihrauch's Computable Abalysis - An introduction. There are short tutorials on the topic, such as this one, also written by Klaus. $\endgroup$ – Andrej Bauer Jan 31 '18 at 15:54
  • $\begingroup$ @orlp: there is no problem with equality. Higher-order intuitionistic logic has the usual equality. I suspect, though, that you are confusing "expressing that $A$ and $B$ are equal" with "algorithmically deciding whether $A$ and $B$ are equal". There is a big difference. And it is unreasonable to require that equality always be decidable. You don't do it for functions int -> int, do you? $\endgroup$ – Andrej Bauer Jan 31 '18 at 15:56
-1
$\begingroup$

This is a hard question to answer, given the vagueness of your notion of "parameter". For example, a typical real number as it is defined mathematically cannot be represented in a computer, using any number of standard arguments (see, e.g. the answers to this question).

Does this mean that a real number has an infinite number of parameters? In particular, your circle example is also faulty, since you need already 2 reals to represent one (which, as mentioned, are not representable).

If you then object that you are only interested in parameters which are themselves representable on a computer, then yes, all data structures that only require a finite number of parameters to describe can be represented on a computer. But this seems to beg the question a bit.

In general, all computable data structures are representable by an idealized VN computer, though often one has to decide how to represent the elements before determining whether they are computable. This paper by Casanova and Santini seems to address some of those issues, but it presupposes knowledge of the mathematical notion of computability.

Finally, I should note that figuring out the number of parameters to represent geometric objects like circles, parabola, etc is a very popular question in algebraic geometry which falls (mostly) outside the purview of computer science.

$\endgroup$
  • $\begingroup$ It is false that a "typical real number cannot be represent in a computer". $\endgroup$ – Andrej Bauer Jan 31 '18 at 7:38
  • $\begingroup$ @AndrejBauer not if typical is meant to be "with measure 1 in the unit interval" and your mathematics are taken to be classical. Obviously, different points of view may be taken on this stance. $\endgroup$ – cody Jan 31 '18 at 13:37
  • $\begingroup$ Unless you specify more precisly the model of computation and the actual structure of the reals that you have in mind, you cannot make such a claim. What structure are you trying to represent? The set of reals? The field of reals? Are you using Type 1 or Type 2 machines? Classical vs. intuitionistic distinction has little to do with this. $\endgroup$ – Andrej Bauer Jan 31 '18 at 15:51
  • $\begingroup$ By the way, every left computable real $x$ may be represented by the code of a Turing machine that calculates an increasing sequence converging to $x$. There are left computable reals which are not computable, such as $\sum_{n \in H} 2^{-n}$ where $H$ is the halting set. $\endgroup$ – Andrej Bauer Jan 31 '18 at 16:13
  • $\begingroup$ @AndrejBauer take any introduction to analysis textbook, and take the real number system defined in that textbook with the implicit logical framework used. As I'm sure you know, I have rather strong intuitionistic sensibilities, but I don't think pretending that the mathematical mainstream doesn't adhere to a standard classical definition of $\mathbb{R}$ is very helpful in the context of this question (though explaining the distinction would be useful). For any "mathematician on the street", there are objects that cannot be represented in a computer. $\endgroup$ – cody Jan 31 '18 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.