# How is the set of all programs countable?

I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish uncountably many programs?

-
Oh, can you? $\hspace{0cm}$ –  Tara B Feb 20 '13 at 23:06
You can't. There are (plenty of) uncomputable real numbers. –  mrf Feb 20 '13 at 23:06
–  Asaf Karagila Feb 20 '13 at 23:06
Presumably, he means that if you give him an $n$ the program tells you the $n$th digit in some (fixed) base, which lets you "print" a real number sequentially, although, of course, it never finishes printing. @Hurkyl –  Thomas Andrews Feb 20 '13 at 23:10
If you can print any real number, you can also "decide" any set of natural numbers, since if $S$ is a set of natural numbers, you can print $\sum_{n\in S} 10^{-n}$, and the program that prints that number can be used to decide whether any particular $n$ is in $S$. –  Thomas Andrews Feb 20 '13 at 23:13

I don't know your definition of 'program', but I'm fairly sure that any program will be a finite length string of characters over some finite alphabet. For any finite set $X$, the set $X^*$ of all finite length strings over $X$ is countable (by the same sort of argument you would use to show the rationals are countable).

-
Yes. I agree with @Tara B. A program will be nothing but a collection of characters of some arbit length. So, we just take the combination of all of them and count it. But this arbit length can be any integer. So in essence the number of programs should be infinite. –  IcyFlame Feb 21 '13 at 9:28
@IcyFlame: but the question was whether the number is countable, not finite. –  robjohn Feb 21 '13 at 10:11
That's why I was only 'fairly sure'. –  Tara B Feb 21 '13 at 11:24
@Arjang: You can find in Joel D. Hamkins work some papers about infinite time Turing machines, but I'm not sure if they allow an infinite input (it might be the case, because now they can actually read all this input...). –  Asaf Karagila Feb 21 '13 at 11:36
I'm not sure he's really talking about a program with "infinite time" or "infinite output," so much as a program which, given $n$, can return the $n$th digit of a (fixed) real number. He's still horribly wrong about the nature of what a program is, of course. @AsafKaragila –  Thomas Andrews Feb 21 '13 at 13:52

If you are programming in a language having the following restrictions:

1. There are only finitely many characters in the language.
2. Every program is finite.

Then the set of all programs is countable, as it is a subset of all the finite strings in the language which itself is countable.

Also, what does it mean to "print out a real number"? If it has an infinite decimal expansion (e.g. an irrational number) then printing it never halts, is this a legal behavior for your program? If not then certainly you cannot write a program which prints every real number.

If you are allowed to print an infinite length output, and your program is finite then you have to calculate the number somehow, but there is only a countable number of numbers which you can compute their values. So yet again, you cannot print all the real numbers.

-
I think he means something like "for every n, there is an n+1" -- for every n that exists, I can make a program that prints n. Since there are infinite n's, there are infinite programs. Unfortunately, CS is grounded in the real works and physical programs cannot encode graham's number as an integer. –  Ryan Amos Feb 21 '13 at 5:04
@Ryan: Theoretical computer science is a part of mathematics; physical aspects of programming is... less. Obviously if we are interested in what we can encode ourselves then it is obvious one person can only type in less than $2^{100}$ keystrokes in their lifetime, so even if you combine several lifetimes of typing you still only covered a minute amount of possible numbers. But this is not the question here. –  Asaf Karagila Feb 21 '13 at 11:09
@Arjang: Either you have to compute that string; or you have to encode it into the program. In either case you can only have a countable collection of outputs. –  Asaf Karagila Feb 21 '13 at 11:28
@alan: Who said he did? I think Graham said in some interview once that he only know a few of the last digits or something like that. –  Asaf Karagila Feb 22 '13 at 20:23
True, only the tail is known, Wikipedia > Graham's number –  alancalvitti Feb 22 '13 at 20:39

The set of all programs is countably infinite. To see why, first notice that each program must be finite in length. Second, notice that the set of all possible programs is infinite, for no matter what $n \in \mathbb{N}$ you pick, you can always write a program that is longer than $n$. Next, let $S_n$ be the set of all programs of length $n$. Each $S_n$ is finite. The set of all programs of all possible lengths is a countable union of sets $S_n$:

$$S = \bigcup_{n=0}^\infty S_n$$

Since the countable union of countable (or finite) sets is at most countable, we conclude that the set of all programs is countable.

-

In a programming language that works by translating whole compilation units (such as source files) at a time, the set of possible programs is countable. An infinitely long stream is not considered a valid program, because the compiler never terminates and so there is never an executable form.

In a programming language which can interpret (or compile, on the fly) an indefinitely long stream of code (such as from an interactive session), and produce useful behaviors before reaching the end of the stream, the set of programs is uncountable.

So, for example, the set of possible interactive Lisp sessions (which are de facto programs) is uncountable, whereas the set of possible C programs is countable.

Each finitely long program corresponds to an integer, and so there can be a one-to-one mapping between programs an integers. Infinitely long programs correspond to the real numbers.

-
It is not clear to me that indefinitely long streams of code (such as from an interactive session) actually exist. Only finitely many key strokes have actually been entered on all the keyboards ever manufactured. –  Jay Feb 20 '13 at 23:27
@Jay: I would be surprised if "the compiler terminates" was in the C++ standard's definition of a well-formed program. –  Hurkyl Feb 20 '13 at 23:36
@Jay by that reasoning, $\pi$ doesn't exist, because only finitely many digits have ever been calculated and printed out. –  Kaz Feb 20 '13 at 23:39
Turns out there was some wording in C++98 which said that a C++ source file must terminate with a newline character. (Which implies that it must terminate.) Evidently, that wording has been removed. The grammar of C++ can clearly produce programs of infinite length. For example, an infinite stream of external declarations such as extern int x; is syntactically valid C++. A parser can keep parsing such a stream without memory growth. The problem is that the parser never declares acceptance. It just never raises a diagnostic. –  Kaz Feb 20 '13 at 23:44
+1 for being the only answer to separate code from data, which the question asker has conflated. The number of possible programs is finite, but given an infinite stream of data, the number of possible actions the program can take is infinite (assuming it can act before reading all the data - like grep can). –  Izkata Feb 21 '13 at 4:06

See this answer, or any of the other fine answers to that question. (Ignore the bad answers.) Not every real number is computable, so you can't do what you're proposing.

-

Because we can think each program we write is a small specific-purpose Turing machine. The classical Turing machine do its job based on the input and its current state inside and so do our programs. Reference

And The set of all Turing Machines is countable. Hence the set of all programs is also countable.

I believe correct tags are missing the question more belongs to computational-theory. or Theory of computation

-

for every real number, you can create a program that prints out that number

Why do you claim that? It is false. In order to print out a number, you need to be able to express that number in the programming language. If you claim that every real number is expressible, it's up to you to show how to encode arbitrary real numbers in the programming language of your choice.

An evident way to express real numbers, which is offered by many programming languages, is to write them in base 10, with a decimal point. This only allows expressing numbers that can be written with finitely many digits after the decimal point (decimal numbers), since a program is finite (if you allow infinite programs, what you call a program is not what everyone else calls a program). Many programming languages further restrict to a bounded number of digits (often in base 2 rather than base 10) so they can only represent a finite subset of the real numbers.

There are languages where you can represent more numbers. For example, some languages have no bound on the size of integers. A given implementation may run out of memory, but that's because this implementation is only an approximation of the actual language. Some languages put no limit on the size of manipulated data, and they can be implemented with the provisio that for any given program and, you may need to provide a sufficiently large computer (as opposed to other languages such as C which require you to commit to a memory size before you write the program). Lisp and Haskell are two examples of languages that support arbitrary integers ($\mathbb{Z}$), as well as arbitrary rationals ($\mathbb{Q}$).

Some (rather non-mainstream) languages can express arbitrary computable reals. By definition, any number that is expressible in a programming language that can exhibited explicitly is computable. For example, Coq has a type for reals, as does Isabelle/HOLhere's a definition of $\pi$ in Coq. In both cases, the real numbers that can be expressed are actually a subset of the computable reals, restricted by the ability to not only write a program that computes a number but also prove the termination of that program within the framework of the language (both languages only contain terminating programs and membership in these languages is decidable, so by Rice's theorem they reject some terminating programs).

The set of all programs is countable because every program can be written as a finite string over a finite alphabet. This is in fact the easiest way of proving the existence of non-computable reals: for every computable real, there is a program that computes it, and distinct reals are of necessity computed by distinct programs. Since there are only countably many programs that compute numbers, there are only countably many computable reals. But the set of all reals is not computable, so there are uncountably many non-computable reals.

No, I can't point you to a non-computable real. They exist, but by definition, the ones I can describe are the computable ones. You can exhibit a non-computable real using a diagonal argument (pick a numbering of the countable reals written out in decimal, and change the $n$th digit of the $n$th number). This proof is not constructive because the existence of a numbering sequence does not have a constructive proof.

-

When you abstract it, a program is basically just a map $m$ from the binary input sequence $I=(i_1,i_2,...,i_{n_i})$ to the output sequence $O=(o_1,o_2,...,o_{n_o})$. Since you can encode an arbitrary binary string as an integer, you can express the sequences by integers as well, i.e. $I\hat\in\{0,1,...,2^{n_i}\}$ and $O\hat\in\{0,1,...,2^{n_o}\}$ such that

$$m: \{0,1,...,2^{n_i}\}\to\{0,1,...,2^{n_o}\}, I\mapsto m(I)=O.$$

There are $2^{n_i}$ different possible inputs for each of which there are $2^{n_o}$ possible outputs, yielding a total of $2^{n_o 2^{n_i}}$ possible maps.

So as long as these two sequences are finite in length (and your common program deals with finite bit strings), the set of all possible maps (read: programs) is finite as well.

As you see from the comments, the case where your program treats countably many infinite input or output bits (take a true random number generator for example), is a different beast that yields indeed an uncountably infinite amount of possible programs.

-
The number of maps from a countably infinite set to a countably infinite set is uncountable. Did you mean finite instead of countable? –  robjohn Feb 21 '13 at 10:13
@robjohn I definitely made an error, countable set mappings aren't necessarily finite. But before I fix this, why is the number of maps from countably infinite to countably infinite sets not countably infinite as well? –  Tobias Kienzler Feb 21 '13 at 10:59
@Tobias: The number of maps from $\Bbb N$ to $\{0,1\}$ is already uncountable: these maps are just the indicator functions of subsets of $\Bbb N$, so there is an obvious bijection between them and $\wp(\Bbb N)$, which of course is uncountable. And making the codomain larger than $\{0,1\}$ does not decrease the number of possible maps. –  Brian M. Scott Feb 21 '13 at 11:29
@Tobias: Neither the input nor the output is really relevant to the question of how many programs there are: that’s a function of the number of symbols available, the restrictions on how they may be combined, and the restrictions on the length of a program. In the present context there are at most countably many symbols, and the length is required to be finite, so there are at most $\aleph_0^0+\aleph_0^1+\aleph_0^2+\ldots=\aleph_0\cdot\aleph_0=\aleph_0$ possible programs. –  Brian M. Scott Feb 21 '13 at 12:52
@TobiasKienzler A program is not just a lookup table, so it is very bad form to identify it with the graph of the function it computes. –  Zhen Lin Feb 21 '13 at 13:11

You say: "since for every real number, you can create a program that's prints out that number".

This is not true, unless you allow programs of infinite length, and the set of these is uncountable.

-
what about finite length programs requiring infinite memory? then it will be a trivial task. –  Arjang Feb 21 '13 at 11:18

All the answers to fit the question number of programs are countable use the discrete finite definition of program , using either finite memory, finite ( countable ) instruction etc.

How ever in the old analog days where voltage was considered as output it was a trivial task to construct a circuit that prdouced all the possible voltage between 0 and 1. Now of course some physics savvy people would point out that voltage is discrete therefor you really dont end up producing all the real numbers as a voltage output between 0 and 1. But that is a physical constraint.

So yes a classical program with all of it's finite/countable restriction on memory, instructions etc. can be shown to end up as a point in countable set.

But an analog machine, like the ones constructed by pullies and ropes by Mayan's can indeed produce all the real numbers between 0 and 1, rest of the real line could have been achieved by a multiplication factor ( again some type of pully and rope computation).

So the statement that set of all the programs is countable depends on what is the computation model that it is being set in, otherwise it neither true or false.

-
Given this interpretation, the original question is easy to answer: people are referring to the usual meaning of "program", rather than referring to an unstated esoteric alternative. –  Hurkyl Feb 21 '13 at 15:16
Along these lines, why bother with a machine? The retrieval of the "answer" is inherent in the measurement system. Just assign the length of a ruler to equal the desired number in arbitrary units and call it "computed." (Physically obtaining two or more real numbers with a given relationship, though, seems impossible to me. But mathematically the distinction may be meaningless.) –  Potatoswatter Feb 21 '13 at 17:10

You may need to visit http://phy.unn.edu.ng for more information on the Mathematical approaches needed to tackle this.

-
Welcome to MSE! This is better left as a comment as answer should have helpful hints or actual answers as opposed to link pointers. Can you add more specifics as to what you are actually referring to? Regards –  Amzoti Mar 20 '13 at 17:26

Well ,why don't we define a program as a circuit rather to give us an output of one's and zero's?

That is i am saying that rather than looking at the program at the highest level only. Lets look at what a program does at the physical level. All it does its take a set of 1's and 0's as input and then give us another set of 1's and 0's as output. So, the question will now change to whether the number of sets of 1's and 0's is finite or not?

Obviously this will be again be infinite. as the cardinality of this set of 1's and 0's will be an integer and the number of integers will be infinite so, again we can say that the number of programs is indeed infinite.

Though i don't understand what is the definition of uncountable.

We normally say that the grains of rice in a pack are uncountable which is blantantly wrong as if i had the time and motivation i could definitely(very easily too i might add) count the exact number of grains in say 1 kg of rice.

Thus the concept of uncountable is in itself flawed and gives a wrong perception about things. According to me only one which is infinite can be considered as uncountable.

-
This answer doesn't make any sense. –  Zev Chonoles Feb 22 '13 at 8:05
why does it not make sense? –  IcyFlame Feb 22 '13 at 8:06
The concept of countability is a well-defined and quite thoroughly studied mathematical concept. The mathematical meaning of words does not always match their everyday meanings (e.g., unlike a door, a subset of a topological space can be both open and closed). It is best to use mathematical definitions when answering questions on this site. –  Arthur Fischer Feb 22 '13 at 8:25
@IcyFlame: Did you look at the link in Arthur Fischer's comment? In mathematics, 'countable' doesn't mean 'you can simply count it', because that's not a precise enough notion to be mathematical. In particular, in normal English you would probably never say you could count an infinite set of objects, but in maths an infinite set can be countable. –  Tara B Feb 22 '13 at 15:34
@IcyFlame: You could ask a question on this site about the mathematical definition of uncountable, since the answers to another question aren't really the right place to discuss it. –  Tara B Feb 22 '13 at 15:36