An interesting way of producing positive integers

It's very unlikely, even if you remove exponentiation and leave only addition and multiplication.

As Erdos said of the Collatz conjecture, "Mathematics is not yet ready for such problems." The difficulty is the mixture of addition and multiplication, which leaves the problem with little exploitable structure. Other very difficult problems of this nature, in addition to the Collatz conjecture, include the Goldbach conjecture, the infinitude of primes of the form $x^2+1$, etc.

While I'd be surprised if there were an easy way to exactly compute the degree of a number, you can of course try to prove bounds. One obvious improvement to p.s.'s, for composite numbers: $$\deg(n) \leq 1+\log_2 \omega(n) + \log_2 \max(P(n), Q(n))$$ where $P(n)$ is the largest prime in $n$'s prime factorization and $Q(n)$ is the largest power.

The problem with just addition is already a hard problem and the subject of much research. The keyphrase to search for is addition chain.