First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I am a bit confused about this. There are classes where using logical synthesis, Karunaugh maps, state encodings, flip flops etc. one is able to construct hardware consisting of logic gates and flip-flops which realizes the desired DFA. Basically all processes that runs on the computer (no matter if is written in C# or Assembler), are at the lowest level realized through logical gates, zeros and ones. So it seems that programs firstly needs to be converted (by compiler I suppose) to some form as I've described. This might imply that every problem that is solvable using C# is solvable using FSM. But this is in contradiction to Chomsky hierarchy and all this theory related stuff, which says that you cannot do the same magic with regular expressions (which are based on FSM) that you can do on Turing machine (which is equivalent of any programming language, if I am wrong correct me please). Moreover, if flowcharts (or even C#, Java ... source codes) were equivalent to FSM why we do not have all software formally verified so far? There is mathematical apparatus for FSM and related stuff, so why do not formally verify everything and ensure the correctness? What I am missing here?
-
1$\begingroup$ Here there are some answers: cs.stackexchange.com/questions/10357/… $\endgroup$– ParhamCommented Nov 20, 2013 at 23:34
-
$\begingroup$ To Patrick87. Thank you very much for answer, I have learned something interesting. When you said that C# is weaker model than FSM, does it mean that anything that is written in C# can be modelled using FSM? Can you post some example where FSM can be used and C# cannot? How should I interpret your words? Just imagine simple switch-case statement in C# which represents states of FSM, vice-versa imagination is out of my mind. Also why actual C# computers are not TM equivalent, I assume that is has something to do with fact that TM assumes infinite length tape (memory). Thank you. $\endgroup$– Wakan TankaCommented Nov 21, 2013 at 17:04
-
$\begingroup$ Re @Patrick87's comment: A real PC has limited memory, thus its possible states form a finite set. The operation of the hardware (is supposed to be such that) each state uniquely defines the following state. Thus your kick-ass PC is really just a DFA. $\endgroup$– vonbrandCommented Jan 29, 2014 at 22:45
2 Answers
Converted comments to answer.
FSM is an ambiguous term but is often taken to mean "finite automaton", of which deterministic finite automata (DFAs) are representative. These are strictly less powerful than Turing machines and other Turing-equivalent systems of computation. That said, actual computers running C# programs are not Turing equivalent; in fact, they're a strictly weaker model of computation that finite automata, although many interesting finite automata can be modeled exactly, and many Turing machines can be simulated accurately. PC < FSM ~ DFA < TM.
Suppose that your PC has 1 TB of memory (RAM, registers, stack, HDD, etc.) This is 8796093022208 bits. Your computer can exist in 2^8796093022208 unique states. It is therefore incapable of recognizing any regular language whose minimal DFA contains more than 2^8796093022208 unique states. One such language is the language containing the first 2^8796093022208 words over a unary alphabet (when ordered lexicographically).
-
$\begingroup$ OK so TM is the most robust because it have infinite memory right? But I'm talking about limited resources. The TM that you can simulate on C# is limited with PCs RAM. In this point of view is TM equivalent to C#? $\endgroup$ Commented Apr 27, 2016 at 22:18
As Patrick87 mentions, FSMs could mean several things, depending on context. They can be used to refer to DFAs, to NFAs, and perhaps even to PDAs. Flowcharts are something different altogether. They describe the flow of control in a computer program. They can be used either informally, say when describing an algorithm, or formally, say to do static analysis in a compiler. In the latter case they are a (possibly annotated) directed graph. DFAs and NFAs are also annotated directed graph, but the semantics are different. DFAs and NFAs have a very specific semantics that describes how to execute them. Flowcharts are an abstraction of some features of the computation, but don't necessarily describe it fully; when they do, they are usually more expressive than FSMs. Indeed, FSMs are read sequentially, each edge consuming one input symbol. In contrast, flowcharts describe arbitrary instructions. The input is consumed at will, perhaps even at random order.
In contrast to Patrick87's answer, I see no reason to read flowcharts with a real machine in mind. Flowcharts usually make sense for an abstract machine whose variables and memory are unbounded, and in that sense they are a representation of a Turing-complete computation model, though perhaps an incomplete representation. They are more powerful then FSMs. For example, you can consider the following flowchart, with four states S, END, YES, NO and the following informally described transitions:
- There is an "initial" transition pointing at S annotated "$x=y=z=0$".
- There is a self loop at S annotated "read $a$; increase $x$".
- There is a self loop at S annotated "read $b$; increase $y$".
- There is a self loop at S annotated "read $c$; increase $z$".
- There is an edge from S to END annotated "end of input".
- There is an edge from END to YES annotated "$x=y=z$".
- There is an edge from END to NO annotated "otherwise".
This is similar to an FSM since it does consume one character at a time. However, the side effects are different since variables are kept, and the language computed by the machine is not context free (can you figure it out?). Flowcharts are even more general since they don't have to read a character at every step.
Summarizing, both FSMs and flowcharts are described by annotated directed graphs. That's a common modelling device, but it exhausts the connection between the models.
