How is the set of all programs countable?

Question

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?

Answer 1

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).

Answer 2

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.

Answer 3

From my answer here.

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

proof: set of all Turing Machines is countable

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

Answer 7

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/HOL — here'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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

A computer program is not just a string of bits. It is a string of bits coupled with a machine (classically FSA, PDA, LBFA, Turing Machine, and higher order stuff). There is uncountable number of different computer langauges. Even at the level of language and alphabets it is not hard to show that there are an uncountable set of langauges defined on a finite alphabet (which is a good start:). But here I can construct something even simplier as a thought experiment:

Suppose we have the Apple 3.1415626536... This is a theoritical machine with a programming langauge that defines opcodes (say for fun from a 6502 CPU Instruction set) and supports a memory model that has registers and memory blocks that hold items of any required size and can be addressed by addresses of any size (these assumptions are no more unrealistic than those of a turning machine with its infinite tape)

Such a machine takes any number in the reals and scans down the string of bits until the bit pattern matches an op code. Then it loads an operand until it encounters a special op-code that represents end-of-line. The instruction may need to load up more than one such operand but the micro-code for this cpu can do this.

In this way all real numbers function as code for this computer whose control logic is clearly finite although its data path not so much.

But this example demonstrats merely one such computer/language that has valid programs that consists of all members of a uncountable set

[]

Answer 12

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.