How would one prove that whether a Linearly Bounded Automaton (i.e a Turing Machine where the number of tape cells you can visit is not infinite but is bounded by the size of the input, i.e if the input has size n, you can visit only n tape cells, there is a right endmarker on the tape after the input ends that you cannot cross) runs in polynomial time is undecidable? I have a homework question and I can't for the life of me figure out how I'd do this.

Even if we don't consider LBAs, how would I show the undecidability of this for Turing Machines in general, i.e how would I show that it is undecidable to find whether a Turing Machine runs in polynomial time.

I was given a hint, that says "encode the Halting problem for regular Turing Machines. Given a Turing Machine M and input x, where we want to find out if M halts on x, construct an LBA N, which on any input y, erases y, and does something interesting with M and x." I can't for the life of me figure out what the "interesting thing" is supposed to be. I know that the total number of tape cells which M can access is bounded by the size of the input y, but I don't know what else to do here.

One possible approach I've tried is to construct the LBA N to halt and accept/reject iff the execution of M on x stops at most n steps, and to enter a trivial loop iff it takes more than n steps. But, this does not give me the proper implication I need. I need to construct an LBA that runs in polynomial time iff M halts on x, and does not run in polynomial time iff M loops (i.e does not halt) on x. However, with this construction, we only get the result that M loops on x implies that N does not run in polynomial time (because it loops on the input), however, I cannot prove the opposite implication, i.e M halts on x implies that N runs in polynomial time.

One more thing that's throwing me off was that since you only have a fixed number of input cells you can visit, let's say n, which is the size of the input y to the LBA, and if the size of input x is larger than n, then you have no way to simulate M on the full input x, what would I do in that case? Also even if the size of the input x is smaller than n but it's some machine that writes an output much longer than n, then what am i supposed to do? I can't possibly end up actually simulating the full work of the TM, so what would I do?

  • $\begingroup$ Can you tell us in what context you encountered this task? What have you most recently learned? Did you encounter it in a textbook? If so, can you credit which chapter and exercise number? $\endgroup$ – D.W. Nov 25 '20 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.