Can a finite Turing machine model itself?

59 Views Asked by At

Given the following constraints, can a finite Turing machine (FTM) model itself?

  1. An FTM receives only data initially stored on its tape;
  2. The amount of initial data on the tape is limited to $D_{m}$ bits;
  3. An FTM has a tape of length M bits where M>>$D_{m}$.
  4. When the tape requirements of any program run on the FTM exceeds some $M_{limit}$ bits, the program halts and produces a null result.

I suspect that the answer is "no", because:

  1. Let the FTM that is modeling itself be called the “base FTM”; and the model it's running be called the “model FTM”. I suspect that $M_{limit}$ for the base FTM would need to be larger than $M_{limit}$ for the model FTM. 2.If the model FTM were loaded with the same program that runs on the base FTM, it seems that its tape requirements would grow until it reached $D_{m}$ bits, thus limiting the precision with which the base FTM could be modeled.
  2. If the model FTM were given the task of predicting the behavior of the base FTM, and the base FTM were programmed to do the opposite of whatever the model predicted, the system could never halt.