Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct

[Albert van der Horst]

In article <4f654042$0$29981$c3e8da3$5496439d at news.astraweb.com>,
Steven D'Aprano  <steve+comp.lang.python at pearwood.info> wrote:
>On Sat, 17 Mar 2012 17:28:38 -0600, Michael Torrie wrote:
>
>> Thank you.  Your example makes more clear your assertion about "labels"
>> and how really A1 and A5 were the only real labels in the example.
>> Though I still do not really see why "states" is not a good equivalence
>> for labels in this case.
>
>Program labels are states.
>
>You can treat every line of code as being invisibly labelled with the
>line number. (Or visibly, if you are using BASIC back in 1975.) Clearly
>"the interpreter is executing at line 42" is a state distinct from "the
>interpreter is executing line 23", but that state *alone* is not
>sufficient to know the overall state of the program.

This is the idea of the original (not universal, hard coded) Turing
machine with cards. Of course you then still need the infinite tape
to store calculation input and output.

>
>Adding an explicit GOTO label does not change this.
>
>But this refers to the state of the interpreter, not the state of the
>program being executed, and either way, is not a state in the sense of a
>finite state machine.

I hope the reference to the Turing machine makes this clearer.
Turing Machines and Finite State Machines are different constructions
in automaton theory.

Remember those definitions are like

A Turing machine is a set <S, T, F, G, Q >

        S the set of symbols <blank, 0, 1>
        T a mapping of S onto IZ (natural numbers)
        ...
        F is a mapping from SxT into G
        ..

Some such.

(A FSM is just different <A,B,C..Z> with different mappings )

The memory of the Turing machine is T , the tape, time dependant.
The program of the Turing is e.g. F, to be thought of as hard wiring.

A Turing machine is *not* a stored program computer!
The universal Turing machine is, it contains a hardwired program
to execute a stored program on the tape.

>
>--
>Steven

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert at spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst