I had a thought. Define that:
Vague Definition 0. A problem consists of:
- a set $X$
- a set $Y$
- a function $f : X \rightarrow Y$
- a way $\overline{X}$ of representing the elements of $X$
- a way $\overline{Y}$ of representing the elements of $Y$
For example, the problem of working out whether or not $3$ divides $n$, where $n$ is an arbitrary natural number represented as a decimal, might be formalized as follows:
- $X=\mathbb{N}$
- $Y=\mathbf{Bool}$
- $f(x) = 3 \mid x$
- $\overline{X} = $ "the base $10$ representation of natural numbers"
- $\overline{Y} = $ "I guess writing $\mathbf{Bool} = \{0,1\}$ kind of tells you how to represent the elements of $\mathbf{Bool}$."
Vague Definition 1. Let $P=(X,Y,f,\overline{X},\overline{Y})$ denote a problem. Then a solution of $P$ consists of an algorithm $\overline{f} : \overline{X} \rightarrow \overline{Y}$ such that the underlying function of $\overline{f}$ is $f : X \rightarrow Y$.
For example, the aforementioned problem can be solved as follows: if $x$ is a natural number whose base $10$ representation is $\overline{x}$, then we define $\overline{f}(\overline{x})$ by the following procedure: we repeatedly replace $\overline{x}$ with the sum of its digits in base 10. For instance:
$$981 \Rightarrow 9+8+1 = 18 \Rightarrow 1+8 = 9$$
Once we're down to $1$ digit, we check whether or not the final digit is one of $\{0,3,6,9\}.$ If it is, $\overline{f}$ returns $1$. Otherwise, it returns $0$.
(This shows that $981$ is indeed divisible by $3$; indeed, $981/3 = 327$.)
The issue is that when I try to make this more formal, I get stuck pretty quickly. Lets begin with:
Definition 0. Let $X$ denote a set. Then a way of representing the elements of $X$ consists of:
- a set $A$, called the alphabet of the representation.
- an injection $X \rightarrow A^*,$ called the representor.
So for example, the base $10$ representation of natural numbers has alphabet $\{0,\ldots,9\}$, and the representor $\mathbb{N} \rightarrow \{0,\ldots,9\}^*$ is the map that turns a natural number into the string of numerals that represents that number in base $10$.
Okay, at this point I'm stuck. In particular, what should it mean to say that $\overline{f}$ is an algorithm $\overline{X} \rightarrow \overline{Y}$, and how can we define the "underlying function" of an algorithm?
Question. Can these definitions of the words "problem" and "solution" be formalized, and if so, has this been done? If so, where can I learn more about it?
Some further thoughts:
It seems to be the case that absolutely free algebras come equipped with a canonical representation for their elements. For example, the natural numbers can be described as the initial algebra on the signature $$0:N,\qquad S:N \rightarrow N.$$ If they're defined in this way, it canonically equips them with (a slightly inefficient version of) the unary representation of natural numbers. E.g. $$4 = S(S(S(S(0))))$$
Many free algebras also seem to be equippable with natural representations. For instance, the concept of a reduced word gives us a way of representing the elements of free groups.
This is studied in the theory of computability, especially in computable analysis, because the choice of the representation of real numbers determines which functions on real numbers are computable.
What follows is based on Computable analysis: An introduction by Klaus Weihrauch. See also The Representational Foundations of Computation (draft) by Michael Rescorla for a philosophical discussion on the subject, in particular on the question of distinguishing “admissible” notations from “deviant” ones (for which intuitively non-computable functions become computable).
Weihrauch fixes some finite alphabet $\Sigma$ and defines (Definition 2.3.1) notations of a set $X$ as surjective partial functions $\nu\colon \Sigma^*\rightharpoonup X$. (It makes sense to go in this direction, since this function maps the meaningful elements of $\Sigma^*$ to their semantic value.) If the domain is taken to be the set of all infinite strings $\Sigma^\omega$, he talks of a representation instead (used in particular for real numbers). He calls a naming system either a notation or a representation.
Then, given sets $X$, with naming system $\beta\colon \Xi\rightharpoonup X$, and $Y$, with naming system $\gamma\colon\Upsilon\rightharpoonup Y$, and a partial function $f\colon X\rightharpoonup Y$ (he doesn’t give a name to what you call a “problem”), he defines (Definition 3.1.3) a ($\beta,\gamma$)-realization of $f$ to be a partial function $g\colon \Xi\rightharpoonup\Upsilon$ such that for all $s\in\mathrm{dom}(f\circ\beta)$, $$f(\beta(s))=\gamma(g(s)).$$ A “solution” in your sense is thus a computable ($\beta,\gamma$)-realization of $f$ (or, rather, the Turing machine that computes it).