Functions that are Not Efficiently Computable but Learnable
I will formalize a variant of this question where "efficiency" is replaced by "computability".

Let $C_n$ be the concept class of all languages $L\subseteq\Sigma^*$
recognizable by Turing machines on $n$ states or fewer.
In general, for $x\in\Sigma^*$ and $f\in C_n$, the problem of evaluating
$f(x)$ is undecidable.

However, suppose we have access to a (proper, realizable)
PAC-learning oracle $A$
for $C_n$. That is, for any $\epsilon,\delta&gt;0$,
the oracle requests
a labeled sample of size
$m_0(n,\epsilon,\delta)$ 
such that, assuming such a sample was drawn iid from
an unknown distribution $D$,
the oracle $A$ outputs a hypothesis $\hat f\in C_n$
which, with probability at least $1-\delta$, has $D$-generalization error
not more than $\epsilon$.
We will show that this oracle is not Turing-computable.

Actually, we will show that a simpler problem is undecidable:
One of determining,
given a labeled sample $S$,
whether there exists an $f\in C_n$ consistent with $S$.
Suppose (to get a contradiction) that $K$ is a Turing machine
that decides the consistency problem.

We make the following notational conventions.
Identify $\Sigma^*$ with $\mathbb{N}=\{0,1,2,\ldots\}$ via the usual
lexicographic ordering.
For $x\in\{0,1\}^*$, we say that a TM $M$ "S-prints"
$x$ if it accepts all of the strings in $\Sigma^*$
corresponding to the indices $i$ s.t. $x_i=1$
and does not accept (possibly by not halting)
any of the strings
corresponding to the indices $x_i=0$.
Since (by assumption) $K$ is
decidable,
it follows that the function $\tilde K:x\mapsto k$,
defined to be the smallest $k$ such that some TM in $C_k$
S-prints $x$, is Turing-computable.
It further follows that
the function
$g:k\mapsto x$, which maps a $k\in\mathbb{N}$
to the least (lexicographically) string $x\in\{0,1\}^*$
such that $\tilde K(x)&gt;k$, is also computable.

Now define the TM $M$ as follows: $M$ S-prints $g(|\langle M\rangle|)$,
where
$\langle M\rangle$ is the encoding of $M$,
$|x|$ denotes string length, and the recursion theorem
is being invoked to assert the existence of such an $M$.
Then $M$ has some encoding length, $\ell=|\langle M\rangle|$,
and it S-prints some string, $x_M\in\{0,1\}^*$.
By construction, $\tilde K(x_M)&gt;\ell$, and so $x_M$ cannot be S-printed
by any TM with description length $\ell$ or shorter. And yet it is defined
as the S-print output of a TM with description length $\ell$ --- a contradiction.