Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I was also confused then realized that Turing machines that are allowed to write on their tape are not (always equivalent to ?) state machines.

So I guess that making a state machine involves clearly separating the write-protected parts that make it from the rest of the program, and forbidding tampering ?

Also, all computing is not (directly) state machines or even Turing machines : quantum computing and generally analogic computing come to mind.

P.S.: Also, seems like (because of that restriction ?) you cannot have multithreading inside a state machine ?



Here are some comments from the perspective of computing science (i.e. not from the perspective of software development).

There is a conceptual thing called a "finite state machine", which has no memory except a set of finite states. It can, of course, "recognize" the elements of any finite set, but the question is, what infinite sets can it recognize? There is another conceptual thing called a "Turing machine". It has all the same capabilities that an FSM has, plus the ability to read from, and write to, an infinite long tape with a finite set of symbols writable to that tape. Again, the question, what infinite sets can this conceptual machine recognize? Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM. Again the same question.

So, yes, in this context, a TM can do anything an FSM can do, but the converse is very much not true.

That said, real life computers do not have infinite tape; they are actually very very powerful FSMs. So when we talk about the applicability of these ideas to the practical day-to-day writing of software, there are several layers of metaphor involved in why we care at all.


> Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM.

What you've written is correct, but someone who's not reading carefully might mistake "capability" for "capacity". Both pushdown automatons and Turing machines have infinite storage capacity, but the Turing machine can seek to any position in its infinite tape while the pushdown atomaton can only access the top of its infinite stack.


Yeah, as I understand it, this is actually more about emulating a (much more simple) FSM on a (finite, therefore pseudo-)TM ?

And so another thing that I thought would matter for software development is that you should be able to actually make the FSM write "outside of itself" without losing its FSM-ness, in the sense of not being able to later read it - which makes no sense talking generally, but does make sense in this context of emulation ?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: