lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Fri, Mar 29, 2019 at 6:54 AM Viacheslav Usov <via.usov@gmail.com> wrote:
On Thu, Mar 28, 2019 at 8:32 PM Coda Highland <chighland@gmail.com> wrote:

> No, general-purpose computers are Finite Turing Machines, not Finite State Machines.

I am afraid a "Finite Turing Machine" is not a commonly used term, so I am not sure what you are saying here. Regardless, any general purpose computer is trivially an FSM, given their finite alphabets and states.

Er, sorry, I meant deterministic Turing machine, not finite. However, a general purpose computer is not a FSM, because a FSM only has one symbol worth of state (the currently selected state). A PDA adds a last-in-first-out stack. A TM replaces the stack with a seekable tape. A general-purpose computer has random-access storage.
 
> These two formalisms are TWO tiers of computing power apart, with Push-Down Automata existing in between.

The latter have infinite stacks, a luxury that current general-purpose computers cannot afford.

General-purpose computers can simulate infinite stacks/tapes using arbitrary attachable storage. If it runs out, it prompts the user to provide more storage. This means that any algorithm that can be evaluated by a TM can be evaluated by a modern general-purpose computer, with no fixed limits.
 
Coming back to the subject, it is possible to parse just about any grammar with a FSM, given that the input string shall not be longer than a fixed N characters. But it may be (far) more practical to use a different formalism in many cases.

This is trivially true, as you can always construct an FSM with O(k^n) states that hard-codes every possible valid input of length n or less. However, that disgusting complexity means that defining the FSM requires exponential space, which isn't STRICTLY in contradiction with the intent of working within bounded space, but it does a valiant job of TRYING to violate it.

/s/ Adam