patternMajor
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
Viewed 0 times
whyfinitearepowerfulthanmoreautomataturingstatemachines
Problem
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?
Obviously, I'm missing something here. What is going on?
Solution
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.
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.
Context
StackExchange Computer Science Q#74095, answer score: 22
Revisions (0)
No revisions yet.