# #StackBounty: #turing-machines #time-complexity Proving that a time-constructible function to the power a time-constructible function i…

### Bounty: 50

A function \$T: mathbb{N} rightarrow mathbb{N}\$ is time-constructible if there exist a turing machine \$M\$ which computes \$1^{T(n)}\$ on input \$1^{n}\$ in \$T(n)\$ time.

Let \$T_1\$ and \$T_2\$ be two time-constructible functions in accordance to the definition above. I’m unable to prove the following:

• \$T_1(n)^{T_2(n)}\$ is time-constructible

My approach:

• I thought of constructing \$T_1(n)^k\$ using \$T_1(n)^{k-1}\$. Given \$T_1(n)\$ and \$T_1(n)^{k-1}\$ I know I can multiply them in time \$T_i(n)^k\$. Hence the net time to compute \$T_1(n)^{T_2(n)}\$ by my construction = \$T_1(n) + T_1(n)^2 +….+T_1(n)^{T_2(n)} > T_1(n)^{T_2(n)}\$
• To print \$T_1(n)^{T_2(n)}\$ in time \$T_1(n)^{T_2(n)}\$ i would need to print a 1 on the output tape in every timestamp which intuitively sounds impossible to me

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.