5 ms·

You're way off the mark. While it annoys me that computers are constantly modeled as Turing Machines when it's much more appropriate that they be modeled as LB

You're way off the mark. While it annoys me that computers are constantly modeled as Turing Machines when it's much more appropriate that they be modeled as LBAs (Linear Bounded Automata) it does not have a huge bearing on computational feasibility in practice. While LBAs vs. TMs do have entirely different definitions and notions of what is and what is not undecidable (for instance, the halting problem is decidable for computers since they're LBAs. It's just impractical.) this only really becomes a theoretical difference. Suggesting that an x86 PC is limited to the level of computational complexity of regular grammars is just wrong. LBAs are capable of context sensitive grammars and are much more capable than a FSM and absolutely can compute more. In real life, computers can be modeled as turning machines without much issue. Memory is generally Big Enough(tm) that problems undecidable on TMs are terribly infeasible to attempt even though theoretically they are actually decidable. And as long as the problem has a small enough state space, the computational expressiveness is the same. In practice, this occurs often enough that people still call computers turing machines even though they aren't.

xyzzyz 15y ago
Of course it makes more sense to model real life computers as LBAs. Still, it does not change the fact that given a computer, it has bounded, and not linearly bounded amount of memory, and that makes them no stronger than regular expressions. Of course that there's no practical difference for programmers. Of course the problem space is usually small enough. But it only proves my point: applying abstract terminology to real-life stuff does not necessarily make sense all the time. It makes more sense to take. say, C or Python programming environment, instead of x86, as a computing model. It's enough to assume that malloc never fails to have genuinely Turing complete device.
- 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 ago
    Assuming 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]

xyzzyz 15y ago

Of course it makes more sense to model real life computers as LBAs. Still, it does not change the fact that given a computer, it has bounded, and not linearly bounded amount of memory, and that makes them no stronger than regular expressions. Of course that there's no practical difference for programmers. Of course the problem space is usually small enough. But it only proves my point: applying abstract terminology to real-life stuff does not necessarily make sense all the time. It makes more sense to take. say, C or Python programming environment, instead of x86, as a computing model. It's enough to assume that malloc never fails to have genuinely Turing complete device.

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 ago
  Assuming 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]