4
$\begingroup$

I don't know if my question is correct so excuse me if I'm not 100% clear about what I would want to know.

Is there a formalism which can capture all possible algorithms (mathematically speaking) ? Is there an "algorithms" space where algorithms can be expressed (in more than one way may be ?) kind of like vectors in a vector space ?

I mean thinking about it, we can compose algorithms to make more complex ones, apply them sequentially and find simplified versions or may be faster versions of some of them. I might be wrong thinking about it this way, but I see for example the algorithms used to solve the "matrix multiplication" problem such as Strassen's algorithm, the parallel matrix multiplication method and the old naïve version of the algorithm as three representations in the algorithms space of the same individual, or point (the multiplication algorithm) but seen from three different perspectives, having three different spatial and temporal complexities. There might be a way (not discovered yet I suppose) to perform a "problem reduction" procedure to go from one form to another (like a PCA if I may say, but instead of maximizing the variance, we would be aiming at minimizing the temporal complexity given that the complexity of the algorithm itself my become greater (a longer algorithm to write)) I'm just imagining here. I don't think that this level of reduction power or algorithms understanding has been reached yet, but I'm just wondering if the concept itself is approachable from this angle.

So, back to the question and back to the planet earth, is there a universal mathematical formalism for algorithms representation ? (either in a vectors-like form or any other one, may be using an advanced kind of logic)

& Thanks in advance :)

$\endgroup$
  • 3
    $\begingroup$ ... Turing machines? $\endgroup$ – Sal Jan 25 '15 at 23:50
  • 1
    $\begingroup$ Mathematicians kind of like to identify everything that gives the same result in the end - so there's a lot of equivalent formalizations of this. $\endgroup$ – Milo Brandt Jan 26 '15 at 0:41
3
$\begingroup$

In general no, because you can extend your language with oracles which may perform some weird operations (like solving the halting problem). However, Turing machines (or any Turing-complete concept, like λ-calculus, certain cellular automata, etc.) will get you anything you would want in an ordinary setting.

Be aware, that on different computation models you will get different complexities, and some formalisms like circuits which perform computations are, informally speaking, quite far away from Turing machines.

I hope this helps $\ddot\smile$

| cite | improve this answer | |
$\endgroup$

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.