Let $\Sigma$ be an arbitrary alphabet, $\mathcal{P}$ denote the set of all prime numbers, and $\omega := \mathbb{N} \cup \{0\}$ Take the following set.
$$ L = \left\{ (x, \alpha, \beta) \in \omega \times \Sigma^{*2} : \left( \exists t \in \mathcal{P} \right) ~ \alpha^{(x-2)(|\alpha| - 1)} = \beta^t \right\} $$
I was requested to prove that the set is computable in the following way: $a.$ Prove that the predicate being quantified is primitive recursive, $b.$ Prove that the set being quantified over (the primes) is primitive recursive, $c.$ Find a bound for the quantification. Points $a$ and $b$ are simple, but I am having trouble with $c.$
For "a bound for the quantification" I mean some function $f(x, \alpha, \beta)$ s.t. $t \leq f(x, \alpha, \beta)$ whenever $\alpha^{(x-2)(|\alpha|-1)} = \beta^t$ holds for $t \in \mathcal{P}$. The general case is tricky so I thought of dividing in the following cases. Given fixed elements $(x, \alpha, \beta) \in \omega \times \Sigma^{*2}, t \in \mathcal{P}$, and assuming $\alpha^{(x-2)(|\alpha|-1)}=\beta^t$ holds:
- If $|\alpha| \leq |\beta|$ then $ t \leq (x-2)(|\alpha| - 1)$ and this is a bound.
- If $|\alpha| > |\beta|$ however it must follow that $t >(x-2)(|\alpha| - 1)$
It seems impossible to find a bound for $t$ in the second case. Assuming $|\alpha| > |\beta|$, how could we find any quantity $\varphi$ dependent on $x, \alpha, \beta$ s.t. $t \leq \varphi$ whenever $\alpha^{(x-2)(|\alpha|-1)}=\beta^t, t \in \mathcal{P}$?
Hint: I think you are aware of the fact that for $\gamma \in \Sigma^*$ and $m \in \omega$, $|\gamma^m| = m |\gamma|$. So if $\alpha^{(x-2)(|\alpha|-1)}=\beta^t$, ${(x-2)(|\alpha|-1)}|\alpha|=t|\beta|$. Now note that $\left\lceil\frac{|\alpha|}{|\beta|}\right\rceil$ is a primitive recursive function of $\alpha$ and $\beta$ (when $|\beta| \neq 0$). The edge case when $|\beta| = 0$ is simple and can be handled separately.