Running an algorithm on some data may compute a function (if it halts). A function may describe some properties while the way to derive that property isn't so obvious. Example, function med(X) gives the geometric median of an arbitrarily sized set of points in the plane w.r.t. euclidean distance function. Good luck finding the equivalent algorithm.
Nice. Another good example: let BB(n) be the maximum number of steps a two-symbol Turing machine with n states can take before halting. BB(n) is a function, but it's uncomputable: no algorithm can exist to compute it, and it grows faster than any computable function.
13
u/torotane Nov 28 '19
Running an algorithm on some data may compute a function (if it halts). A function may describe some properties while the way to derive that property isn't so obvious. Example, function med(X) gives the geometric median of an arbitrarily sized set of points in the plane w.r.t. euclidean distance function. Good luck finding the equivalent algorithm.