2
$\begingroup$

It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of enumeration and comparison for programs, given a common basis language.

Does there exist an online database that attempts to enumerate algorithms similar to the Human Genome Project according to a basis encoding or language?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Enumerate all algorithms? Why? Most algorithms compute something no one would ever want to compute. $\endgroup$
    – Sasho Nikolov
    Commented Nov 14, 2017 at 6:52
  • $\begingroup$ I posted some links in reply to your question Does there exist an online database of algorithms? in chat. The only major omission I noticed is that parallel algorithms are seriously underrepresented. I probably noticed that omissions only since I currently study parallel algorithms and hardware architecture. So I guess there are other major omissions as well, which I simply don't notice at the moment. $\endgroup$
    – Thomas Klimpel
    Commented Nov 14, 2017 at 10:43
  • 1
    $\begingroup$ Online database? How is that connected to ontology? $\endgroup$
    – Emil Jeřábek
    Commented Nov 14, 2017 at 13:35
  • 1
    $\begingroup$ @SashoNikolov Reifying and relating classes of algorithms can be helpful for teaching and analysis purposes. $\endgroup$
    – CinchBlue
    Commented Nov 14, 2017 at 20:13
  • 1
    $\begingroup$ @EmilJeřábek In bioinformatics, databases with GO and KEGG are commonly used in analysis to relate genes to pathways, diseases, etc. It is a very helpful reference in the field -- I was wondering if a similar thing existed for algorithms in computer science. $\endgroup$
    – CinchBlue
    Commented Nov 14, 2017 at 20:15

1 Answer 1

Reset to default
2
$\begingroup$

[More of an extended comment.]

I think I disagree with the premise of your first paragraph... That being said, while I don't know of a database, there has been some work systematically studying small Turing machines. See Small universal monotone Turing machines, https://cstheory.stackexchange.com/a/20980/129, https://cstheory.stackexchange.com/a/11614/129. While some of this is interesting, I would say it has yet to "bear much fruit (i.e., understanding)." I hope someday it will.

There's also a mismatch between listing small Turing machines and understanding algorithms that are built by people (much as there is still a gap between listing all genes and understanding what they do, though not quite the same). Namely, an ontology of algorithms that are built by people should including things like those mentioned in Thomas Klimpel's comment. (Note: it should also include holographic algorithms, a relatively recent surprise in the ontology of algorithms!) But an ontology of small TMs looks completely different. Given how small a corner of the space of algorithms people have explored, and given the uncomputable problems involved, I highly doubt there would ever be a "complete" ontology of algorithms - either in the sense of small TMs or in the sense of all algorithms people would build. But I suppose having a partial one might still be interesting for some purposes...

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Even a limited ontology can be of great use, as the representation and relations are enough to support a more precise common ground and common language that people can reference. I want to look more into small/bounded Turing machines now -- thank you for the references. $\endgroup$
    – CinchBlue
    Commented Nov 14, 2017 at 23:53
  • $\begingroup$ Also, why do you disagree about with the first paragraph? I don't understand $\endgroup$
    – CinchBlue
    Commented Nov 16, 2017 at 6:53
  • 1
    $\begingroup$ @VermillionAzure: Well, technically I agree, I just don't really know what you mean by "serve as a solid theoretical metric of enumeration and comparison for programs." K is not for comparing programs, its for comparing strings. For enumerating programs, you just enumerate them, you don't need K. For comparing programs, I'm not sure you'd want to use K either, though I guess you could... Very little work has been done on "K for programs," defined as $K(f)$ being the minimum size of a program computing $f$ (in some fixed, prefix-free language, say), though it's an interesting topic. $\endgroup$
    – Joshua Grochow
    Commented Nov 16, 2017 at 17:26
  • $\begingroup$ Every Turing machine is defined on a finite set of language symbols and on a finite number of internal states. Therefore, since its constituents all have a finite quality, it is possible to come up with a finite, discrete representation for it. $\endgroup$
    – CinchBlue
    Commented Nov 16, 2017 at 19:42
  • $\begingroup$ @VermillionAzure: Sure, but that seems to have little to do with Kolmogorov complexity. (Or rather, the definition of $K$ relies on the facts you mention, but the facts you mention existed long before Kolmogorov complexity did.) $\endgroup$
    – Joshua Grochow
    Commented Nov 16, 2017 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.