Introduction

We define the Finite Turing Machine (FTM) as a Turing Machine with a finite tape. In theory means that an FTM is no better than an finite state machine (FSM). But in practice there are advantages and good reasons for using the FTM. This document consists of some of my thoughts on the FTM.

There is a corelation, up to a limit, where we can trade

The states in a state machine are an enumeration of the combinations of states.

Giving a state machine a finite tape allows it to have less states to do the same work. By removing bits from the finite tape, the number of states in the state machine has to grow (probably exponentially) to compensate. Removing all bits from the tape results in a pure state machine. the states can be stored by a simple state machine simulator as bits. These bits are an unorganized enumeration of the original bits of the tape.

Therefore allowing a combination of bits and states can make state machines simpler. Expanding NDFAs to DFAs is foolish; direct conversion to a FTM is acceptable and optimal. The NDFA->FTM can be done in polynomial time.

If transitions in NDFA can be done in the poly time wrt DFA then the advantages of NDFA form make it a preferred format for Turing machines.