# Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?

More precisely, suppose that

for any deterministic TM $M$ accepting $$\text{coBHP}=\{\langle N,x,1^t\rangle\mid \text{ nondeterministic TM N does not halt on input x within t steps}\},$$ there exists some non-halting $\langle N',x'\rangle$ such that the function $f(t)=T_M(N',x',1^t)$ is not bounded by any polynomial.

In that case, given $M$, can $\langle N',x'\rangle$ be constructed by a polynomial time deterministic TM?

For background, see http://eccc.hpi-web.de/report/2009/056/

• Can you define "constructed" more precisely? E.g. are there time constraints on the construction? – Ryan Williams Aug 27 '10 at 1:27
• The time constraint on construction is preferably polynomial time. – Hunter Monroe Sep 7 '10 at 17:55
• I am confused by a few things. When the OP speaks of $f$ being bounded by a polynomial, is he or she referring to the running time of program $M$ on that input? The function $f$ itself appears to map the input to accept/reject. Also, is the polynomial bound now meant to be polynomial in $t$ (as he wrote $t$ in unary), or in $|t|$ (non-unary)? If the former, then the boxed assumption seems just false, since $M$ could simply simulate $N$ on $x$ for $t$ steps, and the run time of this is linear in $t$. – Joel David Hamkins Apr 20 '14 at 23:30
• Joel, I edited the problem to change "NTM" to "nondeterministic TM". Then, the run time of M simulating N on x for t steps is not linear unless P=NP. – Hunter Monroe Sep 29 '14 at 2:43
• OK, this is more clear now; thanks for the edit! – Joel David Hamkins Sep 29 '14 at 13:48

No, such $\langle N', x'\rangle$ is not constructible at all given only a description of $M$, even if you remove the requirement of polynomial time.
Suppose that $CONSTRUCT$ is such a deterministic turing machine outputting $\langle N', x'\rangle$. Note that by your requirement, $N'$ must never halt on input $x'$, no matter how much time $N'$ is allowed to run.
Let $M$ be your favorite deterministic turing machine accepting $\text{coBHP}$. Write a new machine $M'$ as follows:
Input$\langle N, x, 1^t\rangle$ let$\langle N', x'\rangle = CONSTRUCT(M')$ if$N = N'$and$x=x'$then output 1; that is, let$M'(\langle N,x,1^t\rangle)=1$ else, let$y = M(\langle N, x, 1^t\rangle)$ output$y$; that is, let$M'(\langle N,x,1^t\rangle)= y$
That is, $M'$ uses Kleene's recursion theorem to construct a hard input for itself and uses the fact that $CONSTRUCT$ outputs never-halting machines to make that 'hard' input very easy (actually, now bounded by a constant), which is a contradiction. Therefore, $CONSTRUCT$ cannot exist.