Can there be an algorithm for a relation which is not a function?

Question

Functions are relations but all relations may not be functions.Can there be an algorithm for a relation which is not a function?What has theory of computation got to say about relations in general.

Answer 1

Your question is very general, especially it is not clear to me what you mean by "algorithm for a relation". I still have some answers.

The difference between (binary) relations and functions is that the former can have several different outputs for the same input. This is just what non-determinism offers us. Thus the theory of computation offers us many models of computation thatcan be seen as computing relations instead of functions.

Further, the input in the most common models of computations has the form of a string. Thus you could compute a relation in the way that string "(x,y)" is accepted iff (x,y) forms part of the relation. This, of course, generalizes to relations of higher order.

Answer 2

This question is not very clear. Let us assume you are asking about calculating inputs from outputs in case of relations. Consider a relation $R \subseteq A \times B$ is a relation between inputs of type $A$ and outputs of type $B$. There are several possibilities for the meaning of "algorithm $\rho$ computes $R$":

1. For every $x \in A$, $\rho(x)$ outputs some $y \in B$ such that $R(x,y)$. If there is no such $y$ then $\rho(x)$ may be undefined. We may think of $\rho$ as a computable selection or a choice function for $R$, because it chooses for every $x \in A$ some $y \in B$ such that $R(x,y)$.

2. For every $x \in A$, $\rho(x)$ outputs all $y \in B$ such that $R(x, y)$. Here we need to answer how the set $\{y \in B \mid \rho(x,y)\}$ is represented. If we know that there are finitely many such $y$, then we can just list them all. But in general this is going to be a complicated question.

Let us do an example. Consider the case where $A$ is the set of polynomials, $B$ is the set of real numbers and $R(p,x)$ is defined as $p(x) = 0$. That is, a polynomial $p$ is in relation $R$ with a number $x$ when $x$ is a root of $p$. Then:

1. In the first case $\rho(p)$ must calculate one root of $p$, if it exists.

2. In the second case $\rho(p)$ must calculate the list of all roots of $p$.