15
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ As Yuval Filmus mentioned, there are countably many Turing machines. But there are continuum many non-uniform families of boolean circuits, as they can compute any boolean-valued function. But that's probably not what you meant by "algorithm". $\endgroup$ – Reinstate Monica Aug 27 '18 at 17:40
28
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 3
    $\begingroup$ Re: "'Continuum' is probably supposed to mean the real numbers... using 'at least' together with that word is absurdly over the top": There is nothing "over the top" about it, let alone "absurdly" so. There are more sets of real numbers than there are real numbers, so it's quite normal to talk about sets that are larger than the continuum. $\endgroup$ – ruakh Aug 28 '18 at 18:49
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ What does this add to the existing answers? $\endgroup$ – David Richerby Aug 28 '18 at 10:44
  • $\begingroup$ "A proof that turing machines can run all algorithms ... would make this answer unnecessarily long". It would make the answer impossible, since you can't really prove the Church-Turing Thesis $\endgroup$ – John Coleman Aug 29 '18 at 14:41
  • $\begingroup$ @DavidRicherby It adds brevity. $\endgroup$ – user558317 Aug 30 '18 at 21:20
  • 1
    $\begingroup$ @JohnColeman Asserting the impossibility of a proof, without a proof? I meant that a) the OP probably wouldn't care, since b) it's a matter of definition. The question seems to contain the assumption: "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." $\endgroup$ – user558317 Aug 30 '18 at 21:30
0
$\begingroup$

The other answers have already explained that in the standard model of computation (Turing machines, lambda calculus, etc.) the set of algorithms is countably infinite.

However, there are other theoretical models of computation in which the set of algorithms is uncountably infinite. For example, Blum–Shub–Smale machines have an uncountably infinite instruction set1, so their set of algorithms also is uncountably infinite.

1 To be precise, the instruction set itself is finite, but it is parameterized using an uncountably infinite set (the rational functions).

Improve this answer
$\endgroup$
  • $\begingroup$ Aren't the rational functions countable? $\endgroup$ – Ben Millwood Aug 28 '18 at 15:10
  • $\begingroup$ @BenMillwood Can you briefly sketch a proof of why this might be the case? $\endgroup$ – Mark C Aug 29 '18 at 7:41
  • $\begingroup$ @BenMillwood For each $x_0 \in \mathbb{R}$, the constant function $f: x \mapsto x_0$ is a rational function. $\endgroup$ – Florian Brucker Aug 29 '18 at 14:55
  • $\begingroup$ Oh, I was assuming the constants also had to be rational. Never mind then. $\endgroup$ – Ben Millwood Sep 5 '18 at 14:40
-1
$\begingroup$

since turing machines operate with a finite set of alphabet and the tape has to be indexable thus countable

Given a particular size, there are finitely many Turing machines, and there are countably many sizes. A countable set of numbers, as long which are finite, is countable. The size of the alphabet is a factor in the number of Turing machines, but the size of the tape isn't. If the alphabet were allowed to have countably many characters, then there would be uncountably many machines (each real number could be encoded as a sequence of symbols).

If "algorithm" you merely mean a correspondence between input and output, and not a Turing machine or otherwise something that is the normal sense of "computation", then clearly if there a countably many different inputs, then there are uncountably many algorithms: for each real number, we could define an "algorithm" that takes a natural number as input, and outputs that decimal place. For instance, giving the input "3" to the $\sqrt{.5}$ algorithm would give the output of "7". (Note that while it is possible to design a Turing machine that gives the nth digit of $\sqrt{.5}$, it is not possible to do so for all real numbers; only countably many real numbers are computable).

Improve this answer
$\endgroup$
  • $\begingroup$ I don't understand what you're trying to do, here. The question is about the number of algorithms, and the algorithm is the Turing machine, not the input. Allowing infinitely many non-blank characters on the tape at the start wouldn't affect the number of algorithms and, in any case, any terminating run would only be able to read a finite prefix of the input. Meanwhile, your second paragraph is confusing algorithms with mathematical functions. For all but countably many reals, there is no algorithm that can tell you the $n$th digit in the decimal expansion. $\endgroup$ – David Richerby Aug 27 '18 at 21:38
  • $\begingroup$ And what would it mean to have uncountably many algorithms, anyway? You can only write down countably many. In what sense is something that you can't write down an algorithm? $\endgroup$ – David Richerby Aug 27 '18 at 21:39
  • $\begingroup$ @DavidRicherby Yeah, I got a few things mixed up. But one can use "algorithm" in a general sense to refer to a sequence of choices. And in that sense, choosing a digit based on the input is an "algorithm", albeit not a computable one. $\endgroup$ – Acccumulation Aug 27 '18 at 22:29
  • $\begingroup$ In computer science, "algorithm" and "computable" are the same thing. An algorithm is a Turing machine. $\endgroup$ – David Richerby Aug 27 '18 at 22:33

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.