Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What is the enlightenment I'm supposed to attain after studying finite automata?

cstheory.stackexchange.com

Post reply on HN
Print view View original

31–40 of 66 posts

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#31

Post by SecretofMana »

[deleted] wrote: post #30

[deleted]

You did a great job summarizing those topics concisely, but I have some quibbles about the P and NP stuff:

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.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#32

Post by dietrichepp »

javajosh wrote: post #19
jmduke wrote: post #4

Earlier quoted context omitted.

Not to be rude, but what do you mean by this?

Recursion is the key to enlightenment. There are may ways to achieve this recursion, and contemplation of finite automata is one of them. The point of recursion happens when you realize that the thought process which is considering finite automata is itself composed of finite automata. The subjective experience of recursion leads to enlightenment.

Chemical processes are not measurably discrete, so it is only a conjecture that the universe could be modeled as a finite automaton.

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.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#33

Post by dbaupp »

mcmatterson wrote: post #12

Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space,…

It sounds a bit like you are talking about a Turing machine rather than a finite automaton (the latter is much weaker than the former in computational power).

(Not that it matters much, your point still stands.)

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#35

Post by charlesju »

SecretofMana wrote: post #31
[deleted] wrote: post #30

[deleted]

You did a great job summarizing those topics concisely, but I have some quibbles about the P and NP stuff: 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…

Sure, you're probably right. :)

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#37

Post by jacquesm »

andrewflnr wrote: post #16
jmduke wrote: post #4

Earlier quoted context omitted.

Not to be rude, but what do you mean by this?

(Your brain is a finite automaton) + (sliced "cognize" out of "recognize" to get a new word for thinking).

> Your brain is a finite automaton

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).

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#38

Post by bstpierre »

jacquesm wrote: post #26
charlieflowers wrote: post #13

Earlier quoted context omitted.

Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.

Hm, I never thought there would be anybody interested in this stuff so it's all over the place. 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 urgen…

It sounds like we've had similar experiences. I converted a handful of ad hoc "state machines" in a telephony system to FA. The original code was loaded with exceptions and special cases (and bugs). Converting to FA required detailed analysis of the existing system to extract the distinct events and states. I used a tool I wrote [1] to generate C state tables and an event loop from a description of the states+events.

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.

[1] http://bstpierre.org/Projects/smc/

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#39

Post by mcmatterson »

eternalban wrote: post #15
mcmatterson wrote: post #12

Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space,…

> If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register. It would seem an apt analogy for the (basic) Von Neumann architecture, but "modern" CPUs have a hierarchy of "cache lines…

Of course -- the reality of even the simplest CPU is obviously much, much more complex than what I described above. The analogy is really only helpful as a bridge between the world of theory, and the CPU as it exists in the world.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#40

Post by mcmatterson »

eternalban wrote: post #15
mcmatterson wrote: post #12

Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space,…

> If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register. It would seem an apt analogy for the (basic) Von Neumann architecture, but "modern" CPUs have a hierarchy of "cache lines…

Also, I'm interested in what you mean by the correspondence with cache hierarchies. Could you elaborate?
Post reply on HN