12
$\begingroup$

I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines. However, Linearly Bounded Turing Machines are also finite, but it seems that Regular Languages are strictly an improper subset of Context-Sensitive Languages.

Obviously, I'm missing something here. What is going on?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
22
$\begingroup$

The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input.

If the length limit were a constant, then the machine would be no more powerful than a DFA. However, a DFA cannot grow more states to cope with a longer input, which in effect the LBTM can do (taking the state to be the entire machine configuration.) So the LBTM is strictly more powerful.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ There's an interesting result related to this. Any Turing machine that runs in $o(\log \log n)$ space accepts a regular language. $\endgroup$
    – skankhunt42
    Commented Apr 17, 2017 at 18:55
  • $\begingroup$ @skankhunt42, why is that? $\endgroup$
    – Ben I.
    Commented Apr 17, 2017 at 19:11
  • $\begingroup$ @skankhunt42: Correct me if I'm wrong, but…any TM that runs in $k \log \log n$ space must run in $2^{k \log \log n} = 2^{\log (\log^k n)} = \log^k n$ time. But it's not hard to show that any TM that runs in $o(n)$ time decides a language that can also be decided in $\mathcal O(1)$ time. Then there is some constant $c \in \mathbb N$ such that the first $c$ characters of the input determine whether the input is in the language. But then the language is obviously regular: just include a state for each prefix in $\bigcup_{0 \leq i \leq c} \{ 0, 1 \}^i$. Am I missing something? Where's my mistake? $\endgroup$
    – wchargin
    Commented Apr 18, 2017 at 0:44
  • $\begingroup$ @Choirbean It requires a proof using crossing sequences. You can look it up here cs.stackexchange.com/questions/7372/… . $\endgroup$
    – skankhunt42
    Commented Apr 18, 2017 at 7:44
  • $\begingroup$ @wchargin I think the mistake might be claiming that the TM runs in $2^{k \log \log n}$ time because you need to consider the head position of the input tape also while counting the number of configurations. So, I think the TM runs in time $n 2^{k \log \log n}$. $\endgroup$
    – skankhunt42
    Commented Apr 18, 2017 at 7:47
4
$\begingroup$

I think we must first understand the description of a machine and the input size, so that the comparison is of only valid objects. Let say N is a input size. This means machines will have these resource bounds.

\begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell_f & \mbox{Reach finite location: }\ell_f\\ \hline \end{array}

Now, here $\mathcal{M}$ is more expressive than $\mathcal{A}$. That's simply because tape movement and restrictions are limited for $\mathcal{A}$.

Now let's make an invalid comparison. \begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A'} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M \times 2^N & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell'_f & \mbox{Reach finite location: }\ell_f\\ \hline \end{array}

Here $\mathcal{A}'$ and $\mathcal{M}$ have same expressive power. But, note that the size of $\mathcal{A}'$ depends on input $N$ in exponential manner. Earlier size of $\mathcal{A}$ did not depend on $N$. This means for every input to $\mathcal{M}$, you will need to generate new FA, even though $\mathcal{M}$ remains unchanged.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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