1
$\begingroup$

Recently, I was having a debate with a friend about what it would mean to create a machine that ZKSnarks (proves) itself. I tossed the word pure machine out there while describing what I hypothesized would be the manner of state transition for such a machine, alluding to the notion of a pure function. I didn't really know if such a term existed and later decided to read up on automata theory. In doing so, I found the following statement on a Stanford CS page:

Therefore, the major difference between a Turing machine and two-way finite automata (FSM) lies in the fact that the Turing machine is capable of changing symbols on its tape and simulating computer execution and storage.

I understand that finite automata have some machine state. But, with the above in mind, would it be accurate to describe a Turing machine as a stateful system and finite-automata as pure? Is there a better shorthand for the difference as it might pertain to my initial premise?

Improve this question
$\endgroup$
1
  • $\begingroup$ The biggest difference is that a Turing machine has access to an unbounded amount of state, while the amount of state that a finite automaton can access is baked into the design of the machine. $\endgroup$
    – Criticizing Israel not allowed
    Commented Jan 2, 2022 at 18:21

2 Answers 2

Reset to default
5
$\begingroup$

No. The difference between a Turing machine and a finite automaton is in the amount of available work space:

Finite automata are equivalent to Turing machines with finite tapes.

Indeed, any finite automaton can be encoded as a Turing machine that requires no additional work tape. Conversely, a Turing machine whose work tape has finitely many cells has a finite number of possible state-tape configurations and can therefore be encoded as a finite state automaton.

Improve this answer
$\endgroup$
2
$\begingroup$

It depends what you mean by "pure". Without knowing what you mean by it, it seems hard to say. See https://en.wikipedia.org/wiki/Pure_function for one possible meaning. That notion relates to the input-output behavior of the system, and Turing machines and finite-state automata can be viewed as systems that meet those requirements.

It is true that when you look at the sequence of transitions, Turing machines are stateful. So too are finite-state automata: the state is contained in which state of the automaton you are currently in. The overall input-output behavior can still be pure, even if the system modifies internal temporary variables as part of the process of obtaining the final output.

But this may or may not reflect the meaning of "pure" you have in mind, so it may or may not be useful to you.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.