12,080
edits
Changes
Directory:Jon Awbrey/Papers/Differential Analytic Turing Automata (view source)
Revision as of 21:08, 13 March 2009
, 21:08, 13 March 2009→Note 22
To see how each finite approximation to a given turing machine can be given a purely propositional description, one fixes the parameter <math>k\!</math> and limits the rest of the discussion to describing <math>\operatorname{Stilt}(k),</math> which is not really a full-fledged TM anymore but just a finite automaton in disguise.
To see how each finite approximation to a given turing machine can be given a purely propositional description, one fixes the parameter <math>k\!</math> and limits the rest of the discussion to describing <math>\operatorname{Stilt}(k),</math> which is not really a full-fledged TM anymore but just a finite automaton in disguise.
In this example, for the sake of a minimal illustration, we choose <math>k = 2,\!</math> and discuss <math>\operatorname{Stunt}(2).</math> Since the zeroth tape cell and last tape cell are both occupied by the character <math>^{\backprime\backprime}\texttt{\#}^{\prime\prime}</math> that is used for both the ''beginning of file'' <math>(\operatorname{bof})</math> and ''end of file'' <math>(\operatorname{eof})</math> markers, this allows for only one digit of significant computation.
In this example, for the sake of a minimal illustration, we choose <math>k = 2,\!</math> and discuss <math>\operatorname{Stunt}(2).</math> Since the zeroth tape cell and the last tape cell are both occupied by the character <math>^{\backprime\backprime}\texttt{\#}^{\prime\prime}</math> that is used for both the ''beginning of file'' <math>(\operatorname{bof})</math> and the ''end of file'' <math>(\operatorname{eof})</math> markers, this allows for only one digit of significant computation.
To translate <math>\operatorname{Stunt}(2)</math> into propositional form we use the following collection of basic propositions, boolean variables, or logical features, depending on what one prefers to call them:
To translate <math>\operatorname{Stunt}(2)</math> into propositional form we use the following collection of basic propositions, boolean variables, or logical features, depending on what one prefers to call them: