Pedantically speaking of course!
A digital computer is just a Deterministic finite automaton, which of course is equivalent to the complexity [or power] of Regular expressions.
How?
A digital computer just has 2^[memory size] states it can go to. So it is equivalent to a DFA having 2^[memory size] states. So in that sense it is no more powerful than a DFA.
But given that these 2^memory size states are huge, it does approximate a universal Turing Machine!
But to reiterate pedantically speaking it is just a DFA with huge number of states!
No comments:
Post a Comment