1
$\begingroup$

I've been pondering on whether Finite State Machines, particularly Mealy machines, can describe any computable function as Turing machines do. However "Mealy-computability" does not seem to be a term Google likes, and the most I was able to find was an answer in a post of this website:

"Turing Machines have has more computational power than FSM. There are tasks which no FSM can do, but which Turing Machines can do."

Yet no proof as to why.


What is an example of a computable function that cannot be expressed by means of Mealy machines?

$\endgroup$

1 Answer 1

1
$\begingroup$

A Mealy machine (and more generaly a subsequential transducer) is a FSM that preserves regularity, meaning that if $L$ is a regular language and $M$ is a Mealy machine, then $\varphi_M(L)$ is regular.

A Turing machine can transform a regular language in a non-regular language. For example, it could turn $\{a^n\mid n\geqslant 0\}$ (which is regular) into $\{a^nb^n\mid n\geqslant 0\}$ (which is well-known as a non-regular language).

$\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.