0
$\begingroup$

Given an arbitrary TM, can you decide whether it's a LBA?

$\endgroup$
1
1
$\begingroup$

An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is). That is easy to check by looking at the transitions of the TM.

To check if the language is accepted by an LBA is undecidable by Rice's theorem.

$\endgroup$
0
$\begingroup$

No, assume towards contradiction you would have been able to solve it, with some Turing machine $M$. Notice, that it's easy to check given an LBA whether it halts or not (there are a finite number of total possible states) and let's call a TM that solves this by $M'$.

Now, let us construct the new Turing machine $\hat M$ that will solve the halting problem: Given $\langle T,x \rangle$ we want to decide if $T$ halts on $x$.

  • Run $M$ with input $\langle T_x \rangle$, where $T_x$ is a Turing machine that ignores the input and computes $T(x)$.
  • If the answer is false, then also return false.
  • If the answer is true, then we know that $T_x$ is an LBA, and use $M'$ to decide whether it halts or not.

I will leave verifying this proof and completing it to you.

$\endgroup$
5
  • $\begingroup$ Ah yes, I just realised that if it is not a LBA, that warrants it being non-halting, by the used space being constant in the input even if it is strictly larger than the input. But then, is it decidable whether the space used by a TM is strictly less than n, rather than just linear bounded with any factor? $\endgroup$ Apr 5 at 18:34
  • $\begingroup$ Or even if we had another powerful tool, if it was decidable whether a TM used exactly less than or equal than the input space, rather than linear with a constant factor, could that be lead to a contradiction? On the other hand, if these are indeed decidable, what would be a TM to decide them? $\endgroup$ Apr 5 at 19:27
  • $\begingroup$ We can decide whether it takes at most $n$ space: run the machine and see wether it halts or enters a loop without passing the n'th cell $\endgroup$
    – nir shahar
    Apr 5 at 19:35
  • 2
    $\begingroup$ This proof seems wrong. If $T$ halts on $x$ but $T_x$ is not a LBA, then your algorithm outputs false, when it should output true. $\endgroup$
    – D.W.
    Apr 6 at 5:13
  • $\begingroup$ $T_x$ would be an LBA since it only emulates $T$ on $x$ refardless of input. So, given a big enough constant $c$, $T_x$ would halt before reaching the $c$'th cell and thus $T_x$ would be an LBA. Is this reasoning not correct? $\endgroup$
    – nir shahar
    Apr 6 at 10:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.