0

On the Wikipedia article for function problem it currently defines a function problem as follows:

A functional problem $P$ is defined as a relation $R$ over strings of an arbitrary alphabet $\Sigma$: $R\subseteq\Sigma^*\times\Sigma^*$. An algorithm that solves $P$ if for every input $x$ such that there exists a $y$ satisfying $(x,y)\in R$, the algorithm produces one such $y$.

My question is this: why one such $y$ - doesn't a function have unique output?

My guess: Does this have to do with the fact that Turing Machines (one possible instance of a model for computation) will sometimes output strings which differ only by trailing zeros or something, but you want to ignore that in these problems?

Pineapple Fish
  • 1,512
  • relations don't have a unique pairing of $y$ for each $x$. In other words, if $R$ was a function, it would have to return the output of the function for every input – Rushabh Mehta Jun 16 '21 at 18:24
  • @DonThousand then why is it called a function problem? – Pineapple Fish Jun 16 '21 at 18:25
  • 1
    Because the result is a function. The Turing machine outputs one $y$ given input $x.$ So you are taking a relation $R$ and producing a function which is a subset of $R.$ (or really a partial function, which is commonly simply called a function in computability discussions - if there is no $y.$) – Thomas Andrews Jun 16 '21 at 18:28
  • Think of $R$ as a specification of a function. The specification may be loose, i.e, it might allow several different "implementations". E.g., If $xRy$ means $x < y$ for $x, y \in \Bbb{N}$, the solution could be $x \mapsto x + 1$ or $x \mapsto x + 2$ or ... – Rob Arthan Jun 16 '21 at 18:52
  • Perhaps as opposed to "all such $y$," or "at least one such $y$." – saulspatz Jun 16 '21 at 19:26

0 Answers0