35
$\begingroup$

I understand that "structure" of data is totally dependent on Boolean Algebra, but:

Why is data considered to be a discrete mathematical entity rather than a continuous one?

Related to this:

What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

I am not an expert in the field as I am an undergrad math student, so I'd really appreciate it if someone would explain this to me like I'm five.

$\endgroup$

11 Answers 11

44
$\begingroup$

Answer

why was the data considered to be a discrete mathematical entity rather than a continuous one

This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation.

Note that "discrete" does not mean "integer" or something like that. "discrete" is the opposite of "continuous". This means, to have a computer that is truly able to store non-discrete things, you would need to be able to store two numbers a and b where abs(a-b) < ε for any arbitrarily small value of ε. Sure, you can go as deep as you want (by using more and more storage space), but every (physical) computer always has an upper bound. No matter what you do, you can never make a (physical) computer that stores arbitrarily finely resolved numbers.

Even if you are able to represent numbers by mathematical constructs (for example π), this does not change anything. If you store a graph or whatever that represents a mathematical formula, then this is just as discrete as anything else.

Addendum

The rest is just a little perspective beyond the field of computer science. As the comments have shown, the physical topic is not undisputed, and as you can see I have formulated my next paragraph in a way that is rather uncommitted to whether it's true or not. Take it more as a motivation that the concept of "continuum" is not a trivial one. The answer given above does not depend on whether space is discrete or not.

Note that all of this is not so much a problem of computers, but a problem with the meaning of "continuous". For example, not everyone even agrees, or did agree in the past, that the Universe is continuous (e.g., Does the Planck scale imply that spacetime is discrete?). For some things (e.g., energy states of electrons and many other features in Quantum (sic) Mechanics) we even know that the Universe is not continuous; for others (e.g., position...) the jury is still out (at least regarding the interpretation of research results...). (Notwithstanding the problem that even if it is continuous, we could not measure to arbitrary precision => Heisenberg etc.).

In mathematics, studying the continuum (i.e., the reals) opens up a lot of fascinating aspects, like measure theory, which makes it utterly impossible to actually store a "continuous" kind of number/data.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Mar 20 '17 at 16:07
29
$\begingroup$

Computers represent a piece of data as a finite number of bits (zeros and ones) and the set of all finite bit strings is discrete. You can only work with, say, real numbers if you find some finite representation for them. For example, you can say "this data corresponds to the number $\pi$", but you cannot store all digits of $\pi$ in a computer. Hence, computer programs that work with real numbers actually only work on a discrete subset of $\mathbb{R}$.

$\endgroup$
  • $\begingroup$ Digital computers do that, but not analog computers. $\endgroup$ – Drew Mar 18 '17 at 21:58
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Mar 20 '17 at 16:09
8
$\begingroup$

To add to all of these great answers, it's worthy to note that Alan Turing , when defining his machines, argues that the amount of symbols needs to be finite (even if arbitrarily large) since a computer (meaning: a human) could not distinguish all the symbols otherwise.

Here's some excerpts from his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem":

enter image description here

And then on section 9:

enter image description here enter image description here

$\endgroup$
  • 1
    $\begingroup$ Please transcribe the images to they can be indexed by searches. $\endgroup$ – Raphael Apr 15 '17 at 8:16
7
$\begingroup$

It's all in the implementation.

If you think about it, computers really are continuous devices. This is easily shown by the fact that all the EM equations governing how they work are continuous. The thing which is discrete is the models we use to decide how to use these computing devices. The abstract machines we use to describe computation are all discrete.

The huge practical advantage of this is in having independence from a lot of quality control challenges. If our models of computers leveraged the full continuous nature of their transistors and capacitors, then we would have to care about how well we built every transistor to a tremendous degree. We can see this in the audio world. In the world audiophiles inhabit, it's reasonable to spend \$2000 on an amplifier that might have 10 very carefully chosen and matched transistors that do exactly the continuous thing they want. Contrast this with 1,400,000,000 transistors in a Core i7 CPU at the mighty cost of \$400.

Because our computational models are discrete, we can model all of the signals we see in a computer as a discrete signal plus some continuous error term. We can then filter out the errors simply by observing that they aren't the right shape to be part of the discrete signal.

A major part of this is the removal of time terms in our abstract models. Many of our models don't measure time against some physical process, but against some "logical" signal known as a clock. If you interrupt a clock, the system stops moving, but doesn't break down. It just finishes clearing out any analog errors it might have, and sits waiting for the next discrete pulse of the clock. Removing continuous time terms drastically simplifies computation and proofs about computation. Instead, our concepts of time are measured discretely, as seen in P and NP categorizations of algorithms.

$\endgroup$
7
$\begingroup$

Because:

  • Digital computers cannot store arbitrary real numbers.

  • Analog computers are plagued by thermal noise (if electronic), friction (if mechanical or hydraulic), disturbances, sensitivity to temperature variations, inevitable imperfections and ageing. Dealing with such difficulties is what (experimental) physicists and engineers do. Most computer science simply abstracts the physics away.

Here are some papers on real computation:

and here's a paper on analog computation:

$\endgroup$
4
$\begingroup$

The term "computer" in modern parlance means "digital computer"; the essence of a digital computer is that it has a finite number of discrete states. One could have an interesting debate about whether the reasons that digital computers won favour over analogue computers were primarily about engineering practicality, or were primarily due to better underpinning from theoretical computer science. But whatever the reasons, digital computers are what we ended up with, and any useful mathematical model of a digital computer (and therefore its data) is going to be discrete rather than continuous.

$\endgroup$
2
$\begingroup$

The word data derives from the Latin word datum, which means something which was given. Over time the plural form has changed usage and is now commonly used as both singular and plural. It has also come to be associated with information specifically.

Note that there is a difference between an item of information (a datum) and its representation.

Information Theory deals with (amongst other things) discrete pieces of information represented by variables. These are countable entities. For example, velocity, location, mass, and so on are all continuous quantities, but discrete from each other: there is no transformation between mass and location. When these quantities are represented numerically, their data items , however they are represented, are also discrete from each other.

On the other hand, the vast majority of our current computers use some form of electrical charge to represent information. The charge is either present or it is not; there is current in the circuit or there is not. This is also discrete, but it need not be! It is simply because of the way our technology has developed that we use binary representation. It is possible that developments in Quantum Computing will change this in the near future. It is also not inconceivable that analogue computers will make a resurgence and our notions that numbers have to be represented by binary will be washed away!

To summarise: data are composed of discrete items of information, each of which is a datum; whereas each datum does not need to be represented using discrete mathematics, but currently is purely by contemporary coincidence.

$\endgroup$
  • 1
    $\begingroup$ Information theory can also handle continuous variables. $\endgroup$ – Yuval Filmus Mar 17 '17 at 14:42
  • 1
    $\begingroup$ See for example differential entropy. $\endgroup$ – Yuval Filmus Mar 17 '17 at 14:47
2
$\begingroup$

I want to challenge your fundamental premise:

Why is data considered to be a discrete mathematical entity rather than a continuous one?

It isn't.

For example, the study of Algorithms is an important subfield of Computer Science, and there are many algorithms that work with continuous data. You are probably familiar with Euclid's Algorithm for computing the greatest common divisor of two natural numbers, but did you know that Euclid also had a geometrical version of that same algorithm which computes the longest common measure of two commensurable lines? That is an example of an algorithm (and thus an object of study of computer science) over real numbers, i.e. continuous data, even though Euclid didn't think about it this way.

There are many different ways to classify algorithms, but one way that is used, is to classify them by their "continuousness":

  • Digital Algorithms (discrete-event algorithms over digital data):
    • the numerical variant of Euclid's algorithm
    • long-hand division, multiplication, etc. as taught in school
    • any computer program, λ-calculus program, Turing Machine
  • Non-digital data, discrete-event algorithms (algorithms over continuous data, which however still have a notion of "step", i.e. continuous data but discrete time):
    • the geometrical variant of Euclid's algorithm
    • algorithms on real numbers (e.g. Gauss' Elimination Procedure)
    • algorithms on continuous functions (e.g. the bisection algorithm)
  • Analog Algorithms (continuous time, continuous data):
    • electrical circuits
    • mechanical gyroscopes
  • Hybrid Algorithms (any combination of the above)
    • robots

Other answers have already mentioned Real Computation in Computability Theory, another important subfield of Computer Science.

What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

The only real (pun very much intended) drawback is that such data cannot be represented with common digital computers. You can think about algorithms over continuous data, but you cannot run them on the standard machines we usually use to run algorithms.

That's the main reason why continuous data is not as "visible" as digital data.

However, an implementation of an analog algorithm doesn't actually need to be complicated to imagine or even to build. For example, this is an implementation of an analog algorithm:Triumph Cycle bicycleBy Andrew Dressel – Own work, CC BY-SA 3.0, Link

Now, you might say "Wait, that's not a computer, that's a bicycle", but actually, you can use it as an analog computer: it computes the multiplication of a real number $r$ by a fixed rational number $q$. Turn the crankshaft $r$ times and the rear wheel will turn $q×r$ times. You can use this to scale any real number, e.g. turn the crankshaft $π$ times and the rear wheel will turn $q×π$ times; this is something you can not do with a digital computer.

$\endgroup$
  • $\begingroup$ "there are many algorithms that work with continuous data" -- We could have a long discussion if such things should be called "algorithms", but that would be a flamewar about semantics, so let's not. Point is, these are not "algorithms" that run on computers, but on theoretical, formally defined, super-Turing devices. $\endgroup$ – Raphael Apr 15 '17 at 8:18
  • 1
    $\begingroup$ I find the bicycle metaphor misleading. Something that computes one function is not a computer, which we implicitly assume to be universal these days. $\endgroup$ – Raphael Apr 15 '17 at 8:19
1
$\begingroup$

To take a more abstract tack, any possible computation that will eventually give a result, whether on a computer or in your head, can only deal with a finite amount of data. This means that the data can be represented by a string of symbols. This string could be the digits of a number ("42") or the text of a program that creates the data ("4*atan(1)" for $\pi$). The string has to be finite or the entire thing could never be read to run the program.

Now, the set of all possible finite data can be put in lexicographic order, meaning the set is countable. But, the set of continuous real numbers is uncountable, so there are always numbers in the continuum that cannot be stored by a given computation system. From this, we can conclude that the storage of an arbitrary real number requires infinite resources.

$\endgroup$
  • 1
    $\begingroup$ I think this is begging the question. Consider a computer that takes its input from a piece of paper that it examines, and that gives its output on a piece of paper that it draws on. If data were continuous as the OP suggests, then such a computer could be infinitely precise with only a finite amount of data. $\endgroup$ – ruakh Mar 18 '17 at 0:36
  • $\begingroup$ @ruakh Are you talking about something like an analog Turing machine, where it could, for example, read the exact length of a drawn line? $\endgroup$ – Mark H Mar 18 '17 at 1:22
  • $\begingroup$ Yes, exactly. As I understand it, that's the sort of thing the OP is asking about. $\endgroup$ – ruakh Mar 18 '17 at 1:58
0
$\begingroup$

Data is not always considered as discrete. Scientific programming often involves floating-point arithmetic. The programmer usually pretends that the variables involved are continuous, while keeping in mind the issue of numerical stability, which stems from the fact that data is stored to only a finite precision.

$\endgroup$
  • 12
    $\begingroup$ Floating-point is discrete... if a programmer pretends it is continuous, that just means that either the results do not matter, or that the programmer has not understood what he's doing. $\endgroup$ – AnoE Mar 17 '17 at 11:13
  • 2
    $\begingroup$ I respectfully disagree. $\endgroup$ – Yuval Filmus Mar 17 '17 at 11:16
  • 6
    $\begingroup$ @YuvalFilmus alas as floating-point is discrete there is nothing more to say. Each time something is put in an ordinary computer it has been been discretized for. $\endgroup$ – Jean-Baptiste Yunès Mar 17 '17 at 12:04
  • 5
    $\begingroup$ @AnoE it means the results are to be trusted up to a certain precision, that is what Yuval means by "pretends". You can get some usable results, but you have to blur out on the precision. For large sets it makes sense. Contrast this to classic mechanics problems: you know your measurements are not precise. a 3cm object does not have actually 3.000000000~ cm of lentgh. You just cut your measurement's precision at some reasonable point. $\endgroup$ – Mindwin Mar 17 '17 at 14:26
  • 6
    $\begingroup$ I don't think the question is about how our minds work. I think it's about how things actually work. The reason that floating point numbers are approximate is because they are discrete. That you think about them as continuous even though they really are not doesn't help answer the question of why values are discrete in computers. On a side note, your way of thinking can be dangerous. Many a bug has resulted from programmers thinking of floating point as continuous. Even common numbers that we tend to think of as precise such as 1 tenth or 1 hundredth are approximate in floating point. $\endgroup$ – JimmyJames Mar 17 '17 at 16:42
-2
$\begingroup$
  • For a computer to work with data, the data must exist within the computer's accessible memory
  • A computer's accessible memory is finite
  • Only finite data can exist within a computer's accessible memory
  • Non-discrete values are infinite

Data in computer science is considered to be discrete.

$\endgroup$
  • $\begingroup$ What does "non-discrete values are infinite" mean? For example, $\mathrm{e}$ is an infinite non-recurring decimal but it can be specified in a finite way as $\lim_{t\to\infty} (1+1/t)^t$. $\endgroup$ – David Richerby Mar 19 '17 at 21:35
  • $\begingroup$ The formula you specified is shorthand - you could not use it in any calculations whose actual real "answer" is needed and thus no meaningful "work" could be done by the computer. You could write a small text parsing program to take in and spit out textual representations of irrational numbers but the actual numerical representation of those number's "values" cannot be stored in memory - anymore than I can write "this is infinity" on a slip of paper and say I am holding everything in my hand. $\endgroup$ – Repomeister Mar 19 '17 at 23:53
  • 1
    $\begingroup$ You seem to be assuming that the only way to compute on a real number is to produce its decimal expansion. That simply isn't the case. $\endgroup$ – David Richerby Mar 20 '17 at 0:14
  • 2
    $\begingroup$ If you don't have an actual value, are you really "computing"? Absolutely. Any computer algebra package does this all the time. by abstracting the actual values into written fourmulas you can at most show the relationships between entities and not their actual values $e^{i\pi}=-1$ looks like an actual value to me. If the calculations never resolve to an actual value it is just an approximation. Er, so, if I tell you that the area of a circle of radius 2 is $16\pi$, that's "an approximation" but if I tell you that it's 50.265... then that's not an approximation? $\endgroup$ – David Richerby Mar 20 '17 at 9:24
  • 1
    $\begingroup$ @Repomeister The number of marbles would presumably be an integer, so it's a less interesting example -- you don't need real numbers to express it. But computers can do exact math on real numbers, a famous result of Tarski (improved by Ben-Or, Kozen, & Reif in the 80s). In particular, if you write out an expression using integers, comparison operators $<,\le,>,\ge,=,\ne$, the field operators $+,-,\times,\div$, and variables $x_1,x_2,\ldots,x_n$ a computer can decide whether there are real numbers $x_1,\ldots,x_n$ which make the expression true. $\endgroup$ – Charles Mar 20 '17 at 16:40

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.