Skip to main content
Tweeted twitter.com/StackCompSci/status/854166484444229632
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
Ben I.
  • 1.7k
  • 14
  • 26

Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

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?