2
$\begingroup$

Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions.

  1. The first algorithm, by means of some textual reformatting and filling in the usual gaps in high-level reasoning, can be easily (say, within several days of coding) turned into a (relatively large) computer program in some imperative programming language, including that of Turing machines (provided appropriate tooling support, of course).

  2. The second algorithm can almost be turned into code in some imperative programming language, except there are some unknown constants (e.g., the algorithm contains an assignment "$x := c^2$", where $c$ is nonconstructively defined by Theorem 5.19.38, which says $\exists\,c\in \mathbb{N}\colon\dots$). In the best case, this algorithm has some merits such as creating a connection to some other area of mathematics, and in the worst case, this algorithm is simply "'print $r$;', where $r$ is the constant $R(5,5)$". We know that the second algorithm solves our task, i.e., that a Turing machine corresponding to our high-level description exists, but we don't know some part of this algorithm exactly.

In mathematical writing, how do you call these algorithms when you provide the reader with them? I mean, how do you distinguish between them? Do you say explicit/nonexplicit? Effective/noneffective? Any other pair of terms?

Improve this question
$\endgroup$
4
  • $\begingroup$ Look at constructible functions, may be it serves $\endgroup$
    – Bulat
    Jun 27, 2018 at 22:06
  • $\begingroup$ Algorithm is a function, function is an algorithm. I tell about the entire algorithm, which may be considered as non-constructible function as long as we don't proved that there is Turing machine computing R(5,5). The trick is that if we can prove that, we know how to compute this R95,5). Again, i'm not sure. Look yourself, may be there is something just near that. $\endgroup$
    – Bulat
    Jun 27, 2018 at 22:15
  • 2
    $\begingroup$ Assuming you have some way of verifying whether an answer is correct or not (or possibly some relevant intermediate result), then the second description does suggest an algorithm. Namely, try each value of $c$ until you produce a verifiably correct result. The theorem guarantees termination. $\endgroup$
    – Derek Elkins left SE
    Jun 28, 2018 at 3:01
  • 1
    $\begingroup$ Also posted on Mathematics. Please do not post the same question on multiple sites simultaneously. Since this has been done quite a while ago, and there are good answers to both questions, I will take no further action now. $\endgroup$
    – Discrete lizard ♦
    Apr 17, 2019 at 17:24

1 Answer 1

Reset to default
2
$\begingroup$

Personally, I would call the first one an algorithm, and I would call the second a non-constructive proof of the existence of an algorithm. But it probably doesn't matter all that much what you call it, exactly, as long as you are explicit and clear about what you mean.

Related: https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs, https://cstheory.stackexchange.com/q/12162/5038.

Improve this answer
$\endgroup$
0

Your Answer

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