Timeline for Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 18, 2017 at 7:47 | comment | added | skankhunt42 | @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}$. | |
| Apr 18, 2017 at 7:44 | comment | added | skankhunt42 | @Choirbean It requires a proof using crossing sequences. You can look it up here cs.stackexchange.com/questions/7372/… . | |
| Apr 18, 2017 at 0:44 | comment | added | wchargin | @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? | |
| Apr 17, 2017 at 19:11 | comment | added | Ben I. | @skankhunt42, why is that? | |
| Apr 17, 2017 at 18:55 | comment | added | skankhunt42 | There's an interesting result related to this. Any Turing machine that runs in $o(\log \log n)$ space accepts a regular language. | |
| Apr 17, 2017 at 18:32 | vote | accept | Ben I. | ||
| Apr 17, 2017 at 16:02 | history | answered | rici | CC BY-SA 3.0 |