Do you ever use what you learned in Theory of Computing in your code?

Question

I made what I believe to be a pushdown automaton to read some blob data, but as far as actually using computability IN your code, not just to analyze it. Is there any good application of that?

Answer 1

I know we learned about state machines in that class and I find them to be amazingly useful. Regular expressions too.

Answer 2

I can't think of a case where I personally have had a use for pushdown automaton or state machines, but if you ever find yourself implementing a regex library, you're going to want to brush up on your state machine knowledge.

Another field where state machines are often used is in games. Path-finding, AI, and several other fields of game-programming relies heavily on state machines to track the state of all the objects in the game world.

Answer 3

To keep track of protocol states where I work, we model state machines graphically and generate code from that for the proper behaviour. No complexity or computability theory though.

Answer 4

After graduating from college in 1986 where my senior year was devoted to writing a compiler - lexer in the fall, parser in the winter, and code generator in the spring - i was shocked to discover lex and yacc! We didn't use UNIX...

With my new-found toys I write a regular expression parser to build a state machine based on the equivalency of regular languages and finite automata. I plugged those state machines into the keystroke processing in UNIX to prevent users from typing illegal characters in input fields.

It was a really fun project but it tought me an important lesson in UI design - users HATED it! They banged on keys not understanding why it wasn't displaying that character. They much preferred to type gibberish and get an error message later.

Go figure

Answer 5

I feel as if there should be a generic SO answer for this question.
"Is the ITEM_TOPIC that I LEARN_DID in PLACE_OF_EDUCATION really useful?"

It basically begs the question: "Can I just not do this, because it really isn't important?"

99.999% of the time the answer is going to be yes, you should do do your work, because there is potentially some use of the information.

All information has potential use. If you are really asking the: "Do I REALLLLLLLY?" question, then you probably lack the curiosity necessary to be successful in the computer science - software engineering world.

College doesn't teach you everything. Hell, it doesn't teach you much specifically. What it does teach you is how to learn. Learning new ideas/topics/concepts is imperative to be successful in a career with rapidly changing paradigms, such as being a software engineer.

And to be quite frank, broad topic classes (Theory of Computing) are the best Comp Sci classes you can take. The information there applies to the general understanding of computers. Anyone can learn syntax, but few know what the underlying mechanisms are.

Answer 6

Yes, I've found lots of opportunity to put theory to work, in particular when I am building something generalized and abstract.

I've seen a pushdown automaton parser, for some custom language. It was a nicer implementation than recursive decent, but I didn't look closely at the grammar.

Depending on the system, I've used lots of theory, lots of OS worthy algorithms, and some pretty interesting math. Even if you don't use it directly, a good solid sense of Computer Theory will save you lots and lots of time from trying to implement impossible code. Indirectly that's the message behind the halting problem, but I think most people are too weirded out by those classes to try and do anything but get out as quickly as possible.

Computers straddle the border between pure mathematics and the real world. You build complex abstract 'machines' to play with symbolic tokens that represent the real world. Even though most of the ugliness comes from the real world side, if you understand the mathematical side, life is far easier.

Paul.