Dfyjkt

Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms but strategies) but I think thats beside the point for my question.

This got me thinking about the cardinality of the set of algorithms. I have been searching around a bit but have come up with nothing. I've been thinking that, since turing machines operate with a finite set of alphabet and the tape has to be indexable thus countable, it's impossible to have uncountable number of algorithms. My set theory is admittedly rusty so I am not certain at all my reasoning is valid and I probably wouldn't be able to prove it, but it's an interesting thought.

What is the cardinality of the set of algorithms?

An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well describe them as computer programs.

The precise formalism you use doesn't much matter but the fundamental point is that each algorithm can be written down as a finite sequence of characters, where the characters are chosen from some finite set, e.g., roman letters, ASCII or zeroes and ones. For simplicity, let's assume zeroes and ones. Any sequence of zeroes and ones is just a natural number written in binary. That means there are at most a countable infinity of algorithms, since every algorithm can be represented as a natural number.

For full credit, you should be worried that some natural numbers might not code valid programs, so there might be fewer algorithms than natural numbers. (For bonus credit, you might also be wondering if it's possible that two different natural numbers represent the same algorithm.) However, print 1, print 2, print 3 and so on are all algorithms and all different, so there are at least countably infinitely many algorithms.

So we conclude that the set of algorithms is countably infinite.

The set of algorithms is countably infinite. This is because each algorithm has a finite description, say as a Turing machine.

The fact that an algorithm has finite description allows us to input one algorithm into another, and this is the basis of computability theory. It allows us to formulate the halting problem, for example.

at least continuum number of strategies to approach a specific problem

"Continuum" is probably supposed to mean the real numbers... using "at least" together with that word is absurdly over the top. To be a bit tongue-in-mouth: countably infinite is pretty large, but uncountably infinite is... larger than large. Hugely more so. Unfathomably.

So let's throw that out of the window. To see what kind of infinity we are dealing with is dead simple (and intuitive, even if your friend has never heard of any theoretical computer science):

• Any algorithm can be implemented with any turing-complete language; pick your favourite poison of real-world languages (Java, C, ...) to de-mystify this a bit. All of these are equivalent with the theoretical set of algorithms anyone could ever come up with. Note that every algorithm is in itself finite, i.e., there are no algorithms which would take infinitely many symbols to write down.


• Don't think about complicated Turing Machines. Your language of choice uses simple files to store its source code. Every file is a collection of little numbers (a.k.a., bytes). The important thing is that these numbers are most definitely integer, not continuous. (If you are a purist and want to stay in the theoretical regime, replace the word "byte" with "symbol", it doesn't change anything.) If you are afraid about large programs that are distributed across multiple files (and libraries, and other stuff), then just zip them up into a single compressed archive (i.e., a single file).


• Now, you can assign a single integer number to every file out there, bijectively. We simply write the whole mess of bits/bytes of the file one after another, and end up with a very huge number expressed in binary. In the distant past, people actually did that: they printed compiled binary programms as long lists of hex numbers in magazines; you would type them in, but never see them as anything than numbers (often grouped conveniently in 8- or 16-digit sets to make the typing easier).


• So: every program can be represented by an integer number, albeit an arbitrarily large one. The other way round works as well - every integer can immediately and trivially be transferred into a file and thrown at a compiler (obviously, only a small part of those will be valid programs, but that does not matter to us now).


• In the end, programs, and thus algorithms, are a subset of the integers; hence, only countably many can exist.


• N.B., the fact that there are many different implementations of a single algorithm is in our favour, that is, many of those integers condense into (different representations of) the same algorithm. So if the countable infinity was not the smallest kind of infinity already, we would have to worry about the number of algorithms being even smaller, but certainly not larger (i.e., uncountable).

The specific problem was trading strategies (not algorithms but strategies)

I don't know what your friend means with "strategy"; I assume he means something which is kind of like an algorithm, but not quite formulated in enough detail to hack it into a computer? Or which somehow depends on human "intuition" during execution? If so, then these are just irrelevant details. Humanity has not yet found any kind of description of processes that is more powerful or larger than "algorithms" in the sense that we use in CS.

See Gödel Numbering, it is a basic fact in computer science that algorithms are countable, as are by extension recursively enumerable sets.

Algorithms being countable, it is easy to show that there doesn't exist an algorithm to verify every set in a formal system (assign a truth value to a problem). This would be equivalent to assigning an algorithm to every function mapping the set of problems to boolean values. The set of these functions is however uncountable (trivially of same cardinality as the power set of the set of problems, therefore uncountable).

I hope this gives some intuition as to why algorithms have to be "less powerful" than just any function, an thus countable (let's ignore the continuum hypothesis here).

If one does not start out with the requirement that a strategy needs to be implementable with an algorithm, and ignores real-life discretization effects, one could for example accept the following as a parameterized trading strategy:

Take two real number parameters $a$, $b$. Buy if the price of the commodity falls below $a$, sell if it rises above $b$.

Of such strategies, there are clearly continuumsly many. However, of those only countably many can be implemented by an algorithm. The reason is that if $a$ is not lower-computable and $b$ is not upper-computable, then we cannot detect that the conditions are true.

If we conceive of algorithms as computer programs written in binary*, then the number of algorithms is the number of (integer) binary numbers. Thus the cardinality of algorithms is the cardinality of the integers.

*A proof that turing machines can run all algorithms, and that computers can run any program turing machines, would make this answer unnecessarily long. The former may depend on the definition of an algorithm, but I don't think you're using uncomputable trading strategies.