# How to prove that there must be a bijection between two different implementations of the same function

This question emerged in a conversation with a neuroscientist this morning, in which I wondered aloud whether one could prove that if there exists two different implementations of a function then there must exist a bijection between the implementations.

This would be useful for instance, if you wanted to train an artificial neural network to actual sensory input of an organism and ask it to produce precisely the same motor output as the model organism does.

Then with the help of such a theorem, you'd be able to show that while the two functions have the same mappings and are ostensibly implemented differently, there does exist a direct correspondence between what is being accomplished in with linear algebra in your model and the chemical computations in the real organism.

For example, take the function

$$F(x) = \sin x$$

and take the function

$$G(x) = \sum\limits_{n=0}^{\infty} (-1)^n \frac{x^{2n+1}}{\Gamma(2n+2)}$$

For any $x$ we know that $F(x) = G(x)$.

Provided we do not define $\sin x \equiv G(x)$, i.e. perhaps we define $\sin \theta$ implicitly as:

• $\forall x,y,r \in \mathbb{R}:\big\{ \frac{y}{x}= \frac{\sin\theta}{\cos \theta} \implies x^2 + y^2 = r^2 \big \}$ and then prove that the mappings $\sin \theta$ and $\cos \theta$ are uniquely defined by this assertion.

Is it possible to show that the two "implementations" of $\sin x$ must have a bijection. That somehow the formal machinery that allows $\sin x$ to emerge from my implicit definition is actually equivalent to the formal machinery that enables $\sin x$ to emerge from the Taylor series?

What I do not want to show is that the mappings are the same. That I know how to show.

What I want to show and am struggling to express is that the actual formal implementations of the functions are the same. Perhaps both definitions require certain things to happen underground that are symmetric. I don't know.

Can you help me

1. Express this idea
2. Tell me what has been thought about it before (perhaps in theory of computation?)
3. Do so in a way that a pre rigorous guy can appreciate
• Are you essentially asking that if I have a function $F(x)$ and I have two different algorithms to compute $F(x)$, then there must be a correspondence between each "step" in the two algorithms? As in, if I wrote down side-by-side the steps whereby to compute $F(x)$ using the two algorithms, I could draw lines connecting which step corresponds to which step between the two algorithms? Mar 23, 2017 at 23:17
• Possibly. I'm not sure. In terms of formal math I might mean a correspondence in the theorems and definitions between two functions. The theorems themselves essentially develop a definition of the functions in terms of a formal theory. In practical terms, then yes, I mean two algorithms. Mar 23, 2017 at 23:29
• I know very little of the details of formal logic or proof theory, but if I'm understanding you right, it seems like your theorem is false since you can always take more steps than necessary to perform some task (or define some object). To get to my mailbox, I could go straight there, or walk around my house and then go there. If I'm defining a set as $S = \{1,2,3\}$ I could also add in a redundancy and define it as $S = \{1,2,3\} \cap \mathbb{R}$. You can always make something more inefficient. Mar 23, 2017 at 23:41
• Even if you are making it more inefficient, wouldn't it be possible to avoid the redundancy by folding the redundant parts into a net effect. Ex: if one movement sequence is $\{+1, -1, +1\}$ and another $\{+1\}$, we simply consider $+1, -1$ as one step and $+1$ as being formally $0+1$. Maybe what I am saying is that we can always "continuously deform" one definition of a function into an functionally equivalent but definitionally separate function. Mar 23, 2017 at 23:56
• We just find the right partitioning of the algorithm to equivalence. Mar 24, 2017 at 0:01