Turing Machines (TM) and Finite State Machines (FSM) represent different models of computation. Both are capable of computing a large amount, although the TM being more capable, particularly due to its infinite tape.

My interest is in how to transform one to another. If we were to start with their commonalities, we can see how both consist of a finite set of states and rules to transition between them, as well as accepting states. The difference is that a TM has an infinite tape in addition to its state. Often we can take some of the contents of the tape and convert them to additional states. This can be seen as addition can be done on a tape, or by creating multiple states depending on the size of the inputs. As such, we can then take a FSM and give it a tape of its own, albeit one of finite length.

Now we can see that the difference between the two is the length of the tape, a finite for the FSM and an infinite for the TM. As such, we can see that by extending the tape for the FSM, it approaches the TM. That is to say, we can approximate a TM with a FSM if we were to have sufficient working memory, being what the tape is for a TM.

Alternately, we often consider each state of a FSM to be identified by a unique number, and here we can append the working memory to that state number. This can be seen as augmenting the state tree for each case of inputs. If we consider a standard TM, we can prove that it is computationally equivalent to a multi-headed TM, which can use a similar proof to a multi-tape TM. This proof isn’t too difficult, the gist of it being that certain cells, such as every even one, can be considered to be on a second, independent tape. From this we can consider a TM with a head on every cell, as such there is immediate access to read and write every cell. As such we might as well abstract the whole tape into a nuber, which we can, like for the FSM, append to an identifier for the state. This would let us see that the TM is just a FSM with infinite states.

From this we can see that for sufficiently large working memory, and sufficiently small input, a FSM is identical to a TM. The main difference is that the ability of a FSM to cope with arbitrary input is limited, as there is an input which has larger size than the working memory of the state machine.

If there’s something I did incorrectly, or a point I should expand on please let me know. I have only studied in a few classes on theoretical computing and the main one was on complexity rather than computability. And my knowledge of FSM come from electrical engineering, working on implementing them rather than studying their capabilities. Please feel free to comment or discuss anything related to the above with me.