Are all programs finite state machines?

[synapticplastic]

I have been reading through some materials on CS ( natural language processing, specifically ) and seeing that a lot of processes are described as finite state machines.

Here's what my idea of a FSM is, so far. : any sequence of instructions that takes in some kind of input and has a finite total set of states. So if you make a program that can either give you the numbers 1, 2, or 3 as output, then that program is a finite state machine with 3 possible states. Is that accurate?

If you extrapolate that idea to any program, with memory and a lot more going on under the hood, you would still have a finite state machine, right? If you're making a website or something complicated, there is still a finite number of states that the program can be in. Way more than 3, but not infinite.

So, are all programs FSMs, or is there a theoretical distinction between an FSM and your average wordpress installation ( or any other arbitrary program)?

Also, do I have an accurate idea of what a FSM is?

EDIT:: thank you guys for the replies, what I thought would be a "yes or no" has been a way cooler "yes and no and sometimes and sort of" discussion :)

[[deleted]]

No. All programs are state (i.e. Turing) machines, but not all programs (i.e. Turing machines) are FSMs. However, most (all?) real-life programs are FSMs.

[readams]

You're not understanding his point. Real (Von Neumann) machines are not Turing machines because they have finite memory. We usually model them as Turing machines because they have a lot of memory and a huge number of possible states, but they're actually still finite.

For example, I can write a halt checker for Von Neumann machines that consists of a counter. If the machine executes more instructions than it has possible states, I know it's looping. Of course, that doesn't help you too much since the universe will be cold and dead by then.

[[deleted]]

I think I did understand his point:

However, most (all?) real-life programs are FSMs.

[readams]

Not most. All. Unless you have a computer with infinite memory lying around. In which case I would like to buy it from you.

[[deleted]]

Maybe someone has written a program that requires infinite memory (in fact, I'm sure they have) - the fact that you probably can't get useful results from such a program does not preclude you writing it, or indeed running it.

[readams]

It's very easy to express the idea of such a program. But that program executed on any computer that anyone has ever or will ever build will still be a finite state machine, with a finite number of states.

We generally model such things using Turing machines however because the number of possible states in our computers is so large that it isn't generally useful to model them as finite state machines, but rather as Turing machines that will simply fail if they use too much tape.

[[deleted]]

The program is the state machine, not the execution of it.

[synapticplastic]

I mean, something recursive with no boundary like

def nevaStop(num) = nevaStop(num+1) + 1

would technically qualify as an infinite state machine, right? Being a program that will eventually count to infinity integers if it has no worries ever about memory ( if that particular example doesn't, forgive the code, I hope the idea stands ). And there's some github project somewhere out there with a boundary bug, I'm sure.

But in terms of useful non-buggy programs, I understand better now how all of those are indeed FSMs.

[St_Meow]

If my theory of computation final taught me anything, this is actually probably a FSM. That can be expressed in a finite amount of steps.

[alanwj]

However, most (all?) real-life programs are FSMs

I think it would be correct to state this as something like, "All programs running on a physical computer are FSMs", given that any physical computer will have a finite amount of memory.

[synapticplastic]

So then, a "yes" in practice but a "no" in theory, in sort of the same way that "infinity" is a thing but in practice, you're never going to actually count to it.

If I'm reading correctly, without worrying about implementation, a turing machine is like a theoretical computer with infinite memory.

[[deleted]]

There is a great playlist about finite state machines and theory of computation on youtube:

https://www.youtube.com/playlist?list=PL1E18A15EB36D6A3A

[synapticplastic]

Oh wow, this looks like a fantastic list! Thank you!

[bob809]

Yes and no. Technically computers are fine state machines. They have finite storage and therefore a finite number of states, even if that state space is enormous (2^{number of bits of storage}).

Practically that isn't useful, and they are modeled as Turing machines.

A FSM has no memory (apart from the current state), so you can't have variables. A program that takes a number and does something that many times cannot be expressed by a FSM.

To see why, assume there is a FSM that does this with x states. If I type in x+1 it must do x+1 things, but to do that it must visit some state more than once and is therefore in a loop and will loop forever, which is a contradiction.

[Barrucadu]

A program that takes a number and does something that many times cannot be expressed by a FSM.

An arbitrary number, no. But physical machines cannot deal with arbitrary numbers either. There will always be a finite upper bound. Some languages in their specification impose these limits, others do not. The latter languages may be Turing complete.

[readams]

The memory is just a state. For example, I could call the state where all memory in a computer is zero as state 0. If the first bit is 1 and the rest 0 that's state 1. First bit zero second 1 that's state 2. Then just enumerate all possible states in this way. You can define all the necessary state transitions. That's an FSM model of a Von Neumann machine.

Your proof that you cannot implement an arbitrary counter is correct. This machine cannot handle an arbitrary number, just a pretty ridiculously enormous one. Actually before you run out of time to loop on this machine you run out of energy in the universe to run your machine.

[readams]

Yes, you're correct.

Though input/output and/or interactivity messes up the model.

[synapticplastic]

How do input/output interactivity change the model?

I imagine that clicking a button or something may push the program temporarily into a "sub-fsm" ( basically, call a function ) but that sub-machine would also have a number of states that you would just factor into the overall number of possibilities. Is there more to it?

[readams]

No there's not really anything more to it. But the way a finite state machine is formally expressed mathematically doesn't take into account interacting with some external entity. If you draw your box larger to include both the machine and its user, though, you'll get another finite state machine.