Changes

==Note 22==

==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 k and limits the rest of the discussion to describing

Stilt(k), 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,

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.

we choose k = 2, and discuss Stunt(2).  Since the zeroth

tape cell and the last tape cell are occupied with the

bof and eof marks "#", this amounts to only one digit

of significant computation.

To translate Stunt(2) into propositional form we

To translate Stunt(2) into propositional form we

use the following collection of basic propositions,

use the following collection of basic propositions,