patternMinor
Is a computer equivalent to a Turing machine or linear bounded automata?
Viewed 0 times
linearequivalentautomatacomputermachineturingbounded
Problem
Till date I have read that a Turing machine can do whatever a computer can.
Wikipedia Turing machine
mentions that since a real machine can have only a finite number of configurations it is equivalent to linear bounded automata.
Is this true?
Wikipedia Turing machine
mentions that since a real machine can have only a finite number of configurations it is equivalent to linear bounded automata.
Is this true?
Solution
A machine bounded by $\Theta(1)$ memory is a finite state automaton (As a matter of fact, proving that $\textsf{DSPACE}(\Theta(1)) = \textsf{REG}$ is a classical exercise).
We say that "Turing machines can do whatever computers can" because, as long as we keep in mind that real computers are subject to limitations in computational power, it's more useful to think of computers as imperfect implementations of a universal Turing Machine rather than perfect implementations of a finite state automaton.
We say that "Turing machines can do whatever computers can" because, as long as we keep in mind that real computers are subject to limitations in computational power, it's more useful to think of computers as imperfect implementations of a universal Turing Machine rather than perfect implementations of a finite state automaton.
Context
StackExchange Computer Science Q#86557, answer score: 5
Revisions (0)
No revisions yet.