Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

7
  • 6
    Computer + software is a state machine as long as you restrict memory, disk space, and other types of storage (such as internet). As soon as interfacing with internet or other external hardware is allowed (implies unlimited storage), this becomes more like a Turing machine. Ever heard of a phrase 'Turing complete'? Anyhow, functional programs and obj oriented ones both end up as assembly code. I do not know Haskel (a pure functional language)/monads, but there must be an interesting relationship between that and a Turing machine. Commented Jul 22, 2011 at 3:06
  • Adding to Jobs point, any form of non-determinism also exceeds both the state machine and Turing machine models. On the internet, you have multiple non-synchronized machines, data loss through imperfect connections, etc. Even with a single-core simple computer, you have non-deterministic input from the user, but you normally ignore that issue, and pretend all the input was known in advance. Commented Jul 22, 2011 at 3:33
  • @Steve314: Formally, deterministic automata are in a single state. Each input leads to a new state. For non-deterministic automata, each input can lead to multiple states. A non-deterministic automaton with N states can be emulated by a deterministic automaton with 2^N states. Commented Jun 2, 2014 at 17:49
  • @cline - In this case, you're absolutely right, but I think what I had in mind was the kind of concurrency and timing variation that happen in a real-world machine - things like a core running a bit slower because it's too hot, the exact time when the data happens to be under the read head etc. This all fits in the non-deterministic finite automata model you describe, of course, so you're absolutely correct - but the number of states will be insanely huge. I guess I might have had continuous measures such as those temperatures in mind as part of the system state too (not just consequences). Commented Jun 12, 2014 at 21:31
  • @Job Yes, yes there is very interesting relationship between them. Commented Nov 28, 2017 at 2:16