13 ms·
> and that makes them no stronger than regular expressions Again, no. This is simply not how computational complexity works and this statement is factually in
by djcapelis 15y ago
> and that makes them no stronger than regular expressions
Again, no. This is simply not how computational complexity works and this statement is factually incorrect. Please do your research.
- xyzzyz 15y agoAssuming that computer has finitely many states to be in because of finiteness of its memory, we can model it as a very large deterministic finite automaton. You cannot model a real computer as a LBA, because you don't necessarily have as many read-write memory as your input takes. If you think I'm wrong, please, tell me what makes you think that you can model real computers as LBAs.
- deleted 15y ago[deleted]