Premise:
Define a "mindful" Turing machine (MTM) to be a Turing machine (TM) with a log that records the configuration of the head (i.e. current state, symbol being read, next state, symbol to write, and shift) at each step while the machine is running. In addition, an MTM may employ transitions of the form "if [log lists configuration] then [transition]." That is, and MTM "remembers" its past actions and can "choose" its next action accordingly. Call such transitions "unscoped conditional transitions" or "conditional transitions."
Define a "numerate" Turing machine to be an TM with a log which may employ transitions of the form "if [log lists configuration $n$ states ago] then [select this transition]," but not unscoped conditional transitions. That is, an NTM can "remember" its past actions within a particular timeframe and "choose" its next action accordingly. Call such transitions "scoped conditional transitions."
A "forgetful" Turing machine (FTM) is a TM which is neither mindful nor numerate.
A "wise" Turing machine (WTM) is a TM which is both mindful and numerate.
Define two TMs to be equivalent iff for all given starting configurations, the tapes of the two machines are identical upon halting (provided that both machines halt).
Observations:
The following are clear, and an explanation is provided for each:
FTM$\subseteq$MTM$\subseteq$WTM – every MTM which lacks conditional transitions is trivially equivalent to an FTM (since it never reads its log). Every WTM which lacks scoped conditional transitions is trivially equivalent to an MTM.
FTM$\subseteq$NTM$\subseteq$WTM – every NTM which lacks conditional transitions is trivially equivalent to an FTM (since it never reads its log). Every WTM which lacks unscoped conditional transitions is trivially equivalent to an NTM.
Questions:
Are FTMs and MTMs equivalent – i.e. for every MTM, is there an equivalent FTM? If so is there a method for converting MTMs to FTMs? If not, what can an MTM do that an FTM cannot?
Are FTMs and NTMs equivalent – i.e. for every MTM, is there an equivalent FTM? If so is there a method for converting NTMs to FTMs? If not, what can an NTM do that an FTM cannot?
What is the relation between MTMs and NTMs? It is clear that there are steps performed by MTMs that are not performed by NTMs (and vice-versa), but the outputs may be the same regardless of the steps taken to produce them.
Best Answer
These are all equivalent. Basically, a normal Turing machine can record its configuration history elsewhere on the tape; or, if you're using a multi-tape Turing machine, on one of the "auxiliary tapes; or, you can work in a larger-than-normal symbol set which allows you to "double-use" cells (e.g. using a symbol set $\Sigma\times\Gamma$ you can think of a configuration of symbols as a configuration of $\Sigma$-symbols and a separate configuration of $\Gamma$-symbols). That last one is probably the slickest, and a good example of how Cartesian products can be used to clever effect; it also plays an important role in more limited models of computation like finite-state automata (think about intersections of sets accepted by automata).
To get a feel for this, I think it's a good idea to master the proof that two-tape Turing machines are equivalent to one-tape Turing machines; it uses the same basic ideas and is somewhat more streamlined.