What questions become answerable/computable given an uncountable character set?

Question

Having reached the concluding portion of my first course in real analysis, one subject that I feel was not adequately addressed was the issue of cardinalities.

This is a subject I was interested in before taking this course, particularly in some of the stranger aspects and implications of set theory and incomputable numbers. While I personally philosophically question the validity of claiming the existence of something you cannot write down, I understand formally the arguments that leading to the conclusion that there are more real numbers than there are computer programs; i.e. I can translate each possible finite length string of a finite selection of characters into an integer, and then show there is no bijection from the integers to the reals).

My question here is if we are as limited in what we can write down as is typically assumed, namely: this proof assumes there are a finite number of characters. But is this in fact true? Given a piece of paper and a pen, are there really only a finite number of ways to arrange ink molecules on the paper to create a characters? (From my understanding of quantum mechanics, molecules are not limited in possible arrangements in position space; rather it limits the accuracy with which you can know a particle's state in position-momentum space, though this is besides the point).

If there are, in fact, an uncountable number of characters we can write on a paper, does this make every real number computable? Can we make compilers that could handle this, or does this violate some part of the definition of a Turing Machine (with which I am admittedly only vaguely familiar).

I tried a quick google search for this idea, and nothing seemed to come up, so I am curious if this has been explored. I would at the least be very curious to learn about theories of computation under the assumption that we can write programs using an uncountable, or greater, number of characters, and how that might actually work.

Thank you for your answers.

Answer 1

I don't know about your first question, although it seems safe to say that there are only finitely many characters that can be distinguished by human eyes at 1 meter. Similarly, for any particular machine we can build, I think it would only be able to distinguish between finitely many characters written, say, a cell of 1cm by 1cm. If we think of characters as closed subsets of the unit square, then the space of characters is compact in the Hausdorff metric. Therefore given any infinite set of characters, some pair of them will be "very close" in the Hausdorff metric and therefore (I think) practically indistinguishable.

The definition of a Turing machine has nothing to do with actual paper, and regardless of the answer to the first question, the state space and alphabet of a Turing machine are both finite by definition. One could generalize the definition of a Turing machine to allow uncountable state spaces and alphabets, but I don't think that the study of such generalized Turing machines would bear much resemblance to intuitive notions of "computation" for the reason stated above.

Answer 2

If you follow that line of thinking, you don't need any computation to represent real numbers; you can just make a pair of lines denote their distance (in some units). (If you don't want to be restricted by the paper size, you can map $(0,1)$ to $\mathbb R$.)

The conventional theory of computability is developed with the practical restrictions on alphabets in mind. Certainly nothing keeps you from developing a theory of computability in which the cardinality of the alphabet is that of $\mathbb R$. You could then ask for instance which real-valued functions are specifiable in that alphabet. Or you could allow entire graphs of real-valued functions to be used in the alphabet, and then you could ask which more complicated objects, such as functionals of such functions, are specifiable.

Answer 3

Note that this question is as much about physics and engineering as it is about mathematics!

It is a physics question because we are concerned about the "real world", and what mathematical models that adequately correspond to it. e.g. the dot-matrix model breaks down when we start considering length scales around the size of an ink molecule or smaller.

It is an engineering question, because we are concerned with machines actually capable of printing characters, and the ability to distinguish between different characters.

And then once we have adequate descriptions of these, we can consider the mathematical question of how many things are printable, or even dig into more subtle topics such as treating the possibility that different characters might not be fully distinguishable from one another.