Relations between deciding languages and computing functions in advice machines

Question

I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current understanding of the concepts. (I have a project in which I want to discuss Hava Siegelmann's analog recurrent neural nets, which recognize languages in P/Poly, but I'd like to understand and be able to explain to others implications this has for computing functions.)

Suppose I want to use an advice Turing machine $T_1$ to calculate a function from binary strings to binary strings $f: \{0,1\}^* \rightarrow \{0,1\}^*$. $T_1$ will be a machine that can compute $f$ in polynomial time given advice that is polynomial-size on the length of arguments $s$ to $f$, i.e. $f$ is in P/Poly. (Can I say this? I have seen P/Poly defined only for languages, but not for functions with arbitrary (natural number) values.)

Next suppose I want to treat $f$ as defining a language $L(f)$, by encoding its arguments and corresponding values into strings, where $L(f) = \{\langle s,f(s)\rangle\}$ and $\langle\cdot,\cdot\rangle$ encodes $s$ and $f(s)$ into a single string.

For an advice machine $T_2$ that decides this language, the inputs are of length $n = |\langle s,f(s)\rangle|$, so the relevant advice for such an input will be the advice for $n$.

---

Question 1: If $T_1$ can return the result $f(s)$ in polynomial time, must there be a machine $T_2$ that decides $\{\langle s,f(s)\rangle\}$ in polynomial time? I think the answer is yes. $T_2$ can extract $s$ from $\{\langle s,f(s)\rangle\}$, and then use $T_1$ to calculate $f(s)$, and then encode $s$ with $f(s)$ and compare it with the original encoded string. Is that correct?

---

Question 2 (my real question): If we are given a machine $T_2$ that can decide $\{\langle s,f(s)\rangle\}$ in polynomial time, must there be a way to embed $T_2$ in a machine $T_3$ so that $T_3$ can return $f(s)$ in polynomial time?

I suppose that if $T_2$ must include $T_1$, then the answer is of course yes. $T_3$ just uses the capabilities of $T_1$ embedded in $T_2$ to calculate $f(s)$. But what if $T_2$ decides $L(f)$ some other way? Is that possible?

If we are given $s$, we know its length, but not the length of $f(s)$. So in order to use $T_2$ to find $f(s)$, it seems there must be a sequential search through all strings $s_f = \{\langle s,r\rangle\}$ for arbitrary $r$. (I'm assuming that $f(s)$ is unbounded, but that $f$ has a value for every $s$. So the search can take an arbitrary length of time, but $f(s)$ will ultimately be found.)

One thought I have is that the search for a string $s_f$ that encodes $s$ with $f(s)$ has time complexity that depends on the length of the result $f(s)$ (plus $|s|$, but that would be swamped when $f(s)$ is long).

So now the time complexity does not have to do with the length of the input, but only the length of $f(s)$. Maybe $L(f)$ is in P/Poly if $f$ is in P? (Still confused here.)

Thinking about these questions in terms of Boolean circuits has not helped.

Answer 1

I think the answer to Question 2 is "no", as far as we know. For instance, let $f$ be the function that parses its input $s$ as a 3CNF formula $\varphi$ and then returns the lexicographically earliest satisfying assignment to $\varphi$, or $\bot$ if none exists. Then it is easy to decide $L(f) = \{\langle s,f(s) \rangle\}$ in polynomial time, but (assuming P $\ne$ NP), you cannot compute $f$ in polynomial time (and assuming P/poly $\ne$ NP, advice doesn't help).

The following might be a better way to translate between functions and languages. Let $L'(f) = \{\langle s,i,b \rangle : f(s)_i=b\}$, where $y_i$ denotes the $i$th bit of $y$. (I assume that if $y$ has fewer than $i$ symbols, then $y_i=\bot$.) Then if you can compute $f$ in polynomial time, you can decide $L'$ in polynomial time; and if you can decide $L'(f)$ in polynomial time and the length of $f(s)$ is polynomial in the length of $s$, then you can decide $L'(f)$ in polynomial time.