1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I was actually going to ask this as a separate question, but since it immediately follows from your answer: why do we bother distinguishing "states" and "symbols" when we can just use the Cartesian product of the two to the same effect? $\endgroup$
    – R. Burton
    Commented Jul 27, 2020 at 19:51
  • $\begingroup$ @R.Burton You still need different states to govern the machine's behavior. This is because the input to the machine is something the machine doesn't have control over: "state-coding" symbols are things the machine chooses to write, and which it can use later on, but the "starting" symbols are generally just either $1$ or $0$ - and those don't record extra information. Try writing out the details for how a "stateless" machine would be defined and act, and then see if you can implement basic operations (e.g. try to write a "stateless" program which doubles an input string of $1$s). $\endgroup$ Commented Jul 27, 2020 at 19:55
  • $\begingroup$ For example, one common trick you'll want to do is produce strings of $1$s separated by spaces: so "go right until you hit a blank cell, then go to the next blank cell, then print $1$ on that blank cell" or similar. But if we don't have states, this can't be done: "go to the next blank cell" and "print $1$ on that blank cell" are two different actions the program can take when faced with a blank cell, so that's a problem. $\endgroup$ Commented Jul 27, 2020 at 19:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .