[Tutor] what's a state machine?

[Kirk Bailey]

oy vey...

A STATE MACHINE is in effect a computer. It is simulated in code. It is 
customized for the task at hand. A simple state machine would be a 
turing machine if it was 'turing complete'. A turing machine is the 
minimal machine which may be properly called 'a computer'.

I may run off screaming... I  hope someone, ANYONE, can provide some advice.

A state machine is a sequential process which remembers previous STATE, 
and this influences it's behavior. It is programmable, and acts like a 
special purpose computer- or a general purpose one. When it is tailored 
for it's goal task, it is very powerful for that,, and somewhat simpler 
than a general purpose state machine.

Mr Turing came  up with this back in 1936, and it is credited as being 
the first design for a 'electronic' computer, as it could be implemented 
in relays, or vaccum tubes. Mr Babbage's 19th century design was quite 
different, and exclusively baised on mechanical principles, not logical 
ones.

Here is a simple turing machine.
There is only one command, but several subcommands.

It has a memory field for the commands, and another for a data 'tape'. 
This is conceived of as an infinately long paper tape, and some means of 
writing marks to it, erasing marks, READING them, and moving the tape 
left or right one 'step' This could be implemented as a long row of 
bits, for instance, in a large (looped?) memory array-  or cells in a 
list, with the proper code to loop back to the beginning.

The command is stored in memory TWICE. One is read and executed if the 
CURRENT location in the TAPE is a 0, and the other one is read if the 
current location of the tape is a 1.

The command does one thing: it writes the data to the tape, and moves 
the tape one space to the left or the right. WHICH half of the command 
is read and executed is determined by the STATE of the tape cel being 
examined by the head. The command provides the address to be next 
executed; all the cpu logic does is store the data to address the 
program memory. The tape, implemented in electronics, would be a 1 bit 
memory chip addressed by a up/down counter with binary output, and 
someform oc clocking to step it up or down on count.

The commands are formatted as:

        0   |     1
<-> D ADDR | <-> D ADDR

This means DIRECTION (<=left, >=right), D(ATA) (0 or 1) and NEXT 
ADDRESS. The partial command under 0 is executed if TAPE is 0, and under 
1 is executed if TAPE is 1. You can implement a computer this simple in 
relay logic, if you have a large shipping crate of them. Half wave 
recrified AC for a clock source ought to work. The relays of course 
would want filtered DC. Some extra logic to assist in programming and 
preloading the tape is a major assett. Buck Roger's fans might dare to 
implement the design with these newfangled germanium 'transistor' thingies.

Numbers are stored on the tape as uniary numbers. ???


a zero is a 1.
a ONE is a 11.
a TWO is a 111.
a THREE is a 1111.

to add two numbers is simple. Put them next to one another, turn the 0 
between them into a 1, then trim off two 1 bits, and sit still someplace.

Here ia a program to do this:
First, using manaual control hardware, load the blank tape with:
"0000000000000000011011000000000000000000"
           ^
The caret indicates a place on the tape where the read/write head 
starts. If the tape is a loop, we don't care where it is to start, the 
program will loop it to the right until it encounters the beginning of 
the data field.

ADDR        0   |     1
      <-> D ADDR | <-> D ADDR
0000: >  0 0000 |  >  1 0001
0001: >  1 0002 |  >  1 0001
0002: <  0 0003 |  >  1 0002
0003:  X        |  <  0 0004
0004:  X        |  <  0 0005
0005: < 0 0005  |  >  1 0005
X= don't care, never seen.

oooo writes a zero to the sero, moves head to right. Executes oooo as 
next address.

when it encounters a 1, it writes a 1 to the tape (so it does not 
change) and executes 0001 as the next step.

0001 steps through the 1's, and when it finds the intermediate 0 turns 
it to a 1, then goes to 0002.

You can follow it from there. When the thing STAYS on 0005, it's done. 
Turn off the clock source and read the tape manually for the answer to 
the deep mystery of the sum of 2+2.

THAT is a turing machine. It is a complete computer, and can compute 
ANYTHING. Eventually. If you do not go insane first.

And is a complete pain in the ass.

That ends today's compsci knowledge lecture. Asprin may be purchased at 
the vending machine in the lobby.

I coded one in basic several years ago. I may do it in python. Now, I 
may have to.

Where's the scotch?


John Miller wrote:

> Sean 'Shaleh' Perry <shalehperry@comcast.net> wrote:
> 
>> look at htmlparser's code.  What you need is a state machine ......
> 
> 
> "Rodrigues" <op73418@mail.telepac.pt> wrote:
> 
>> Re's can't, I repeat, can't parse text with structure, you need a full
>> parser (state machine) for it. They can be used however to tokenize
>> the text, e.g. recognize the tags
> 
> 
> I wonder if someone could explain what is meant by a "state machine", 
> (and why regular expressions are insufficient for the kind of parsing 
> Kirk needs for his wiki...)? Thanks.
> 
> John Miller
> 
> 
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor
> 
> 

-- 

-- 

end

Cheers!
         Kirk D Bailey

  +                              think                                +
   http://www.howlermonkey.net  +-----+        http://www.tinylist.org
   http://www.listville.net     | BOX |  http://www.sacredelectron.org
   Thou art free"-ERIS          +-----+     'Got a light?'-Promethieus
  +                              think                                +

Fnord.