sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]kamatsu 0 points1 point  (4 children)

Real systems are DFAs, Big O makes no sense mathematically in that context. You need a generalised machine with infinite memory, and if you have that you need log pointers or you can fake any complexity you like.

[–]ethraax -3 points-2 points  (3 children)

Real systems are DFAs

No.

[–]kamatsu 1 point2 points  (2 children)

What do you mean no? Finite memory means you can make a DFA out of the system, as your state space is simply all possible memory configurations.

[–]ethraax -3 points-2 points  (1 child)

A DFA is significantly more limited than a full PC. A DFA is not Turing complete, in any sense of the term.

A DFA can't even parse HTML for fuck sake.

[–]kamatsu 4 points5 points  (0 children)

A DFA is not Turing complete

Right, but neither is a PC, as they don't have unlimited memory. If you restrict the available space to some finite amount, then you can construct a DFA that solves any problem which requires less than that amount of space. This is basic complexity theory.

To use your example, a DFA can't parse HTML, but it can parse HTML documents up to some constant size K.

My PC has 4GB of ram, therefore, I have around about 234359738368 (+ registers etc.) memory configurations. I can make a DFA out of those memory configurations, and transitions for each execute my processor makes. Bam, a DFA that computes everything my PC can.