What is the enlightenment I'm supposed to attain after studying finite automata?
cstheory.stackexchange.com
cstheory.stackexchange.com
Boy, was I wrong. Despite what I'd anticipated, that class ended up being the single most useful CS class that I took. I had the fortune of taking the class with Alfred Aho[1] - I can't imagine a person more qualified to teach a class on computation via automata; he literally thinks in automata.
One day, I mentioned how I'd solved a particular programming problem (not for class) by reasoning about it as if it were a pushdown automaton, and how I was surprised that these techniques were still relevant, even for problems far more high-level than, say, writing egrep. He told me, 'Sometimes when I have a tough problem, I like to think of it as a language recognition problem, and it becomes easier to solve.'
My brain may not be quite as oriented towards state machines as Prof. Aho's is, but that trick has saved me countless times. Like functional programming, it takes a bit of practice to wrap your head around it if you're not used to it, but it can present really elegant solutions to problems that seem daunting at first glance.
Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages.
That and that alone made the problem tractable. (Tractable to me, that is, quite possibly some genius would be able to solve it in many different ways, but this to me only underscores the value of statemachines as a tool).
If you don't mind being taught by Prof Ullman instead, Coursera has a course on Automata coming up https://www.coursera.org/course/automata
Basically what I've done is to model state machines using a bunch of C macros, added a simple event system to drive the state transitions (receipt of message translates into an event) which allows you to run any number of statemachines in parallel inside a single C thread.
The events are prioritized to make sure that urgent stuff gets processed first (such as statemachines terminating).
Imagine turning a very large bowl of spaghetti into a neatly ticking Swiss watch :)
The particular element that made this a powerful tool was the fact that statemachines (unlike function calls) are restrictive, the state-to-state transitions are all known up front and any state changes that are not explicitly allowed are forbidden. This simplifies design and debugging. An extra benefit of doing it this way is that to run the resulting code on a cluster requires only one (relatively, see 'fallacies of distributed computing') simple addition, a way to pass messages between statemachines on different nodes.
The end result of all this is that what was an absolutely gargantuan knot of hard to read code became almost trivial by comparison, each statemachine is so simple that the business logic portion is usually less than a page of code or so (with a few exceptions), and all of the boilerplate is abstracted out and taken care of by the macros.
Statemachines are small enough that they can be tested with ease and can then be glued together using instantiation from within other statemachines.
The main loop of the program reads input and as soon as it has a complete message will instantiate a statemachine to process it and will then send that statemachine the message to set the ball rolling.
I'll see if I can find the time to describe the method in a bit more detail, statemachines communicating using messages is a powerful metaphor for many programming problems and I think it comes into its own when you're making really complicated systems that have to be very predictable and reliable.
Note that even though there are some parallels with threads threads are simply multiple paths of execution running in parallel through the same body of code, statemachines are different in that instead of functions calling other functions statemachines operate on a single chunk of data (called the state) and will note the changes to the state by transiting to a new state. Every program you write is in essence a statemachine but you normally don't make the states explicit, instead you embody the (single) state that you've got in the combination of program counter, stack and data memory. That makes the state rather hard to untangle at any given moment.
Using statemachines explicitly breaks up this giant state vector into smaller ones that operate on much simpler pieces of data using a series of permitted operations, the outcome of which is rigidly defined.
I hope this all makes sense (it's 6:15 am and I haven't slept yet...)
While the state machines that came out of the analysis were a big improvement, they still weren't perfect. We came across a few bugs later on. Using a strict representation of the state machines was a huge advantage in debugging and maintenance. When everything is moving through the same event loop, it's easy to add logging in the form "[timestamp] state A: event X -> state B". Adding a new state or event to the machine (to fix a bug or add a new feature) is much easier when everything is in one place.
In a couple of cases, the state machine started to become large and unwieldy. Usually the cause was that there would be a couple of "meta" states: we'd have states A, B, and C, but then we'd need to represent "states B and C when X is true; states A and B when Y is true". Pulling X and Y into a separate machine simplified the parent state machine -- every X and Y moved into the child divides the number of states in the parent by as much as half. Then the parent can inject events into the child, and the child can fire events back to the parent.
One more thing I ended up adding (that isn't on your list above) is a true string type to the 'C' language (backwards compatible, works with pre-defined strings as well), including garbage collection. I found that in order to get the right level of abstraction the C string type was simply inadequate, it kept forcing things into the foreground that should not even be visible at that level.
The one thing still missing is copy-on-write for string duplication, but that's a pretty tricky thing to implement in a thread safe and portable way. This would give a huge performance boost, but at the moment that would be just another case of premature optimization.
http://www.amazon.com/Introduction-Theory-Computation-Michae...
Though I get the impression you're looking for something a bit more like an oreilly cookbook or nutshell book.
Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems
In particular, it discusses the main implementation strategies and why you'd want to use them. Also, the specific codebase described in the book is excellent. I use it all the time in implementing server software.
[1] http://www.amazon.com/Practical-UML-Statecharts-Second-Event...
It's tough to give justice to this insight, except to say that it really helped crystalize the jump between the theoretical side of CS (which had always been clear to me, if never terribly 'real'), and the applied side of CS (which had always seemed to have evolved in some sort of semi-influenced paralel universe to theory).
I don't know that it's the enlightenment you're looking for, but it's the one that eventually found me.
(Not that it matters much, your point still stands.)
I've seen the FA formalism used in computing theory a few times. Yet, I'm also missing whatever enlightment the author is looking for. But, if for no other reason, it's worth learning just because it's a very nice tool.
If a Turing machine were not defined that way then you'd have to set some upper limit to the size of the tape and that in turn would have odd implications for what would be considered 'computable'. By making the tape infinite by definition you get much more meaningful answers about what is in principle computable and what is not.
Yes, Virginia, you can always obtain more memory.
His only comment was that "Finite Automata are quite weak" (in the context of the _theoretical difference_ between Turing machines and FA). He's absolutely correct. FA can compute a strict subset of what Turing machines can compute.
It would seem an apt analogy for the (basic) Von Neumann architecture, but "modern" CPUs have a hierarchy of "cache lines" that quite neatly -- at least in my mind -- map to a FA "fixed in space" [the cache line], with a "magical tape" [virtual memory and cache coherence].
However the improvement of this construction over any specific FA is that you have a device that can run any FA. As the length of the tape increases you have a device that can imitate the any and all possible FAs.
The CPU is precisely this FA which can imitate any other FA. The tape is memory.
However it is important to note that, at the end of it, any specific program that is being run on finite memory is still an FA.
My bitter example for this is http://stackoverflow.com/questions/11314077/algorithm-for-ex... which question was deleted by moderators, then undeleted by HN members. See http://meta.stackoverflow.com/questions/138678/can-we-please... for the discussion on meta about the question, and http://news.ycombinator.com/item?id=4203350 for the HN discussion at the time.
Incidentally the answer to that question provides a concrete example of something you can easily do if you understand finite automata, that you couldn't do without it, and that knowing how to use pre-built interfaces with finite automata behind them (like regular expressions) would not help you solve.
The remainder is basic to intermediate questions that get answered with "this is a duplicate of X".
It seems like both Wikipedia and Stack Overflow are done, at least approximately. It is just that Wikipedia has at least some structures that have adapted to being done while it seem that SO framework never considered the possibility of the "frontier of general questions" being settled.
The gist: When it comes to computer science and mathematical concepts, don't ask why to study it, just study it - possible applications will probably come at some point later in your career.
A = {0|1,...}
A[x] = !(A[y]•A[z])
That's all there is to computing, near as I've been able to simplify it. Cellular automata may do a better job.
Quantum mechanics is weird to us because we're human-sized and quantum effects are mostly gone at our scale. Therefore, the only language we have for actually doing quantum mechanics is mathematics, so it makes sense to get a firm grasp of the math first. Fortunately, the fundamentals of the math aren't that difficult. I like to think of quantum mechanics as being 'mind-bendingly simple' for that reason.
Scott Aaronson has a fascinating lecture on quantum mechanics seen as a branch of probability theory:
http://www.scottaaronson.com/democritus/lec9.html
> Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let's try to generalize it so that the numbers we used to call "probabilities" can be negative numbers.
I have the reverse problem. The concept of FA makes perfect sense. It's how I naturally think of a computer. It's the theory stuff that is not based on state machnes which I can't get my head around.
So my question is, what enlightenment would I attain if I understood all the theory (instead of just the reality)?
When I write programs, I write state machines.
Deleted comment
1. NP isn't the set of problems that can't be solved in a polynomial amount of time, but rather the set of problems that can be solved non-deterministically in polynomial time. This distinction is important, since this means by definition that P is a subset of NP, and furthermore means that uncomputable problems such as the Halting Problem do not belong in NP.
2. Your definitions for NP-completeness seem mixed up -- the polytime reduction property you're mentioning is the definition of an NP-hard problem, and you've said it backwards. If a problem is NP-hard, every problem in NP can be reduced to it in polynomial time (i.e. it is just as "hard" as every problem in NP). NP-completeness requires in addition to this the property that the problem itself is in NP. For example, although the Halting Problem is NP-hard, it is not NP-complete, since it is not in NP. NP-hardness of a problem can be shown by polytime reducing any NP-complete problem to it, since any problem in NP can be polytime reduced to the NP-complete problem.
It's also nice to be able to express solutions as clearly and succinctly as you can with libraries like this:
https://github.com/cdorrat/reduce-fsm
Not enlightenment, just bliss...
Varying reference frames make it impossible to agree on an order for the input our brains receive, even if we can think of it as discrete. Agreeing on the state of a brain is also impossible, due to relativity.
Quantum entanglement makes it impossible to accurately model a portion of the physical universe, such as a brain. If you want complete accuracy you must model the whole universe or none of it.
I am aware of no accepted model of the universe that is deterministic. Finite automata are deterministic, the brain and the universe are not. Look up "hidden variables".
Only a more sophisticated model than finite automata could possibly be useful for describing physical phenomena in general. All models are wrong, but finite automata are not even useful for describing brains.
That assertion badly needs some proof, and I'm not currently aware that such a proof even exists (but I am aware that there is substantial evidence that it isn't all that simple).
A 'finite automaton' implies that you can capture the complete state vector and for many reasons this is unfeasible. So if there is proof to the contrary then please supply it. (I understand you're merely transcribing the original comment, which to me feels clever but wrong).
1. deep understanding of regular expressions.
2. how to model and reason about complex workflows and business processes.
While I studied FA formally it never really clicked until years later. Sometimes you don't really learn until you are holding a cat by the tail.
I should say that I've always called them "FSM" when, in most cases, in reality I was using a TM. A TM, of course, is also an FSM, so I'm at peace with my loose use of the term.
I really started to use FSM's with great frequency while working on developing hardware with FPGA's. Everything from reset modules to FIFO and SD/DD RAM controllers and more benefit from FSM's. They greatly reduce complexity and allow you to express very complex logic in code that can actually be followed and understood. For some reason FSM's feel more "at home" in hardware rather than software for me (although I use them extensively in software as well). There's something about looking at the definition of an FSM's states and realizing that it's a bunch of single bits (flip-flops) that makes it real:
// Fictitious example
parameter STATE_RESET = 5'b00001;
parameter STATE_STOP = 5'b00010;
parameter STATE_FORWARD = 5'b00100;
parameter STATE_TURN_RIGHT = 5'b01000;
parameter STATE_TURN_LEFT = 5'b10000;
always @ (posedge SOME_CLK) begin
case(state)
STATE_RESET: begin
// Do something in this state
end
STATE_STOP: begin
// Do something in this state
end
STATE_FORWARD: begin
// Do something in this state
end
STATE_TURN_RIGHT: begin
// Do something in this state
end
STATE_TURN_LEFT: begin
// Do something in this state
end
endcase
end
In the software front, everything from communications packet processors to email address validation and menu processors benefit from using FSM's. I like the application of FSM's to web app controllers where you can encode a lot of knowledge and sophistication into your control module and not end-up with a huge rats-nest of procedural code that is nearly impossible to understand and maintain.
I have to admit being guilty of "thinking like an FSM" at times to the extent that I see the opportunity to use them in almost every project, hardware or software.
Again, today I could not imagine designing hardware or writing software without FSM's.
Unless, of course, you're doing an NFA and have a reason to superimpose states (i.e. be in STATE_TURN_RIGHT and STATE_TURN_LEFT simultaneously).
What you are looking at is called "one-hot" encoding.
If you enumerate your states you are asking Verilog to infer a register to hold your states. This also means that you have to have additional (slow) combinatorial logic to identify which state you are in.
With one-hot encoding each state is represented by a single and discrete flip-flop (FF) and no combinatorial logic is required. If you have 33 states the state machine has 33 FF's and only one of them can be "hot" or set to "1" at any given time.
One-hot encoding is faster, and offer a lot of other advantages (ease of debugging, ease of optimization, timing closure, etc.).
Here's a good resource:
http://www.xilinx.com/txpatches/pub/documentation/xactstep6/...
Go directly to Appendix A.
What I really want is an FPGA on a board like the Raspberry Pi, where I can just plug in USB, network and power, copy-paste some code from a tutorial, have it run, and start learning HDL from that point.
I want to be able to develop an FPGA program that can maybe do a specific bitwise computation faster than a CPU or GPU (like SHA hashes for bitcoin mining, but this is just one example) and send inputs and outputs back and forth with a regular computer. Without also having to design and solder my own circuit board in order to do it.
It seems, though, like as soon as you say the word "FPGA," people automatically assume you have a ton of experience and equipment for building your own circuit boards. Which I really don't. And learning this on the same project learning HDL seems like it would really make things kinda hard. "It doesn't work" could mean anything from a solder blob shorting two wires, to some screw-up earlier in the process having destroyed a component and now it'll never work even if you do the rest of it correctly (and you have to increase your budget to replace the now-fried chip), to a failure to understand something about HDL, to some electromagnetic bug in the design of the circuit (like "you need a capacitor here, you need an inductor there, your resistor is 100x too big or too small")...a bug in the HDL of course...or it could be a bug in the USB interface hardware/software I made on the board...or in the custom USB driver I wrote (I've also never actually written a hardware driver before) running on the general-purpose computer...In short, it seems like, to get started teaching yourself hardware design, you have to have approximately one university degree worth of hardware design knowledge already.
Learning HDL, I want to be able to eliminate all of the above sources of error but "if it doesn't work, it must be a bug in my HDL code."
Bootstrapping software programming through self-learning is easy enough that probably at least tens of thousands of middle and high school kids do it on their own every year (I was one of them). Bootstrapping GPU programming is a little harder but still seems doable (I haven't actually done more than dabbling, though). Bootstrapping FPGA should be just as easy, but it isn't.
I haven't been able to find what hardware I should buy to do this, and I haven't even been able to figure out what search terms I should be using. It's been a few years since I looked, though, so maybe I should look again.
http://www.xilinx.com/university/students/index.htm
The issue with doing higher-level work is that you really need to understand circuit design and implementation. A lot of what you do in an FPGA is to type out text that looks like code but in reality is a "secret contract" with the compiler for it to "infer" the circuit you want. In many ways you could say that there are idioms that you learn that will result in specific circuit constructs once they go through one turn of the wheel.
Then there's the issue of optimization. Sometimes you just don't get the performance you want and have to resort to, effectively, hand-wiring stuff in code. Whether VHDL or Verilog, you have the ability to literally hand-wire FPGA internals to build circuits that usually perform or place better than the what the tools can do:
(sorry, this is long)
module ADDER
#(parameter WIDTH = 8)
(
input wire CLK,
input wire CE,
input wire RST,
input wire CIN,
input wire [WIDTH - 1:0] A,
input wire [WIDTH - 1:0] B,
output wire [WIDTH:0] SUM
);
genvar i;
wire [WIDTH - 1:0] xor2;
wire [WIDTH:0] cy;
wire [WIDTH - 1:0] xorcy;
assign cy[0] = CIN;
generate
for(i=0; i <= WIDTH; i=i+1) begin:BIT
if(i != WIDTH)begin:_
myXOR2 x(.O(xor2[i]), .I0(A[i]), .I1(B[i]));
MUXCY m(.O(cy[i+1]), .CI(cy[i]), .DI(A[i]), .S(xor2[i]));
XORCY xc(.O(xorcy[i]), .CI(cy[i]), .LI(xor2[i]));
FDRE f(.Q(SUM[i]), .C(CLK), .CE(CE), .D(xorcy[i]), .R(RST));
end
else begin:_
FDRE f(.Q(SUM[i]), .C(CLK), .CE(CE), .D(cy[i]), .R(RST));
end
end
endgenerate
//synthesis attribute RLOC of BIT[0]._.x is X0Y0
//synthesis attribute RLOC of BIT[1]._.x is X0Y0
//synthesis attribute RLOC of BIT[2]._.x is X0Y1
//synthesis attribute RLOC of BIT[3]._.x is X0Y1
//synthesis attribute RLOC of BIT[4]._.x is X0Y2
//synthesis attribute RLOC of BIT[5]._.x is X0Y2
//synthesis attribute RLOC of BIT[6]._.x is X0Y3
//synthesis attribute RLOC of BIT[7]._.x is X0Y3
//synthesis attribute RLOC of BIT[8]._.x is X0Y4
//synthesis attribute RLOC of BIT[9]._.x is X0Y4
//synthesis attribute RLOC of BIT[10]._.x is X0Y5
//synthesis attribute RLOC of BIT[11]._.x is X0Y5
//synthesis attribute RLOC of BIT[12]._.x is X0Y6
//synthesis attribute RLOC of BIT[13]._.x is X0Y6
//synthesis attribute RLOC of BIT[14]._.x is X0Y7
//synthesis attribute RLOC of BIT[15]._.x is X0Y7
//synthesis attribute RLOC of BIT[16]._.x is X0Y8
//synthesis attribute RLOC of BIT[17]._.x is X0Y8
//synthesis attribute RLOC of BIT[18]._.x is X0Y9
//synthesis attribute RLOC of BIT[19]._.x is X0Y9
//synthesis attribute RLOC of BIT[20]._.x is X0Y10
//synthesis attribute RLOC of BIT[21]._.x is X0Y10
//synthesis attribute RLOC of BIT[22]._.x is X0Y11
//synthesis attribute RLOC of BIT[23]._.x is X0Y11
//synthesis attribute RLOC of BIT[24]._.x is X0Y12
//synthesis attribute RLOC of BIT[25]._.x is X0Y12
//synthesis attribute RLOC of BIT[26]._.x is X0Y13
//synthesis attribute RLOC of BIT[27]._.x is X0Y13
//synthesis attribute RLOC of BIT[28]._.x is X0Y14
//synthesis attribute RLOC of BIT[29]._.x is X0Y14
//synthesis attribute RLOC of BIT[30]._.x is X0Y15
//synthesis attribute RLOC of BIT[31]._.x is X0Y15
<... a bunch more of this snipped due to HN message length constraints ...>
endmodule
//synthesis attribute LUT_MAP of myXOR2 is YES;
module myXOR2
(
output O,
input I0,
input I1
);
assign O = I0 ^ I1;
endmodule
Circuit inference is one aspect of HDL that sets it apart from writing software. To begin with, you are describing hardware and have to be aware of and live within the constraints it imposes. Then there's this inference thing that I've come to call my "secret contract" with the compiler: I say X and we agree that it is going to implement X12345 and we are all happy.
I've implement event-driven FSMs and to me the biggest "ah ah" moment was that it was trivial to make a list of valid (or non valid) state transitions. I used it in one particular case which was really complex (IMHO) to model and were my code was quickly becoming a gigantic mess. I ended up rewriting that part using an event-driven FSM and things became smooth.
Nowadays I don't like the 'S' in "FSM" that much anymore: I've moved to FP and can't really say I'm missing mutability.
data Light = On | Off
toggle :: Light -> Light
toggle On = Off
toggle Off = On
So, the data structures represent the possible states, and the associated functions the transitions.