[geeks] theories of computation

[Joshua D. Boyd]

> Think IMSAI 8080 or SWTP 6800 machine from the 1970's that is a display
> too...

I suppose.  I was specifically thinking about a raster display though.

> So, the problem at hand is:  Is it possible to remain true to the Turing
> machine while having a display and ethernet.  Now, we could map the
> display and ethernet packat buffer to the tape, and create some states
> that do things like update the display to the new display buffer, or send
> the current packet buffer.
> 
> ** Why not? You have just overloaded the operation of
> ** the symbols to include doing things that are not
> ** reflected on the tape - is that a deal killer?

No.  That part is fine.  The problem (or what seems to me to be a problem)
comes below.

> The problem is that the turing machine doesn't have direct memory
> indexing.  All it knows is that it can move back a byte or forward a byte,
> and that presumably there are infinite bytes in either direction.
 
OK, when I had Computational Models (which didn't even mention lambda
calculus, which I will breifly explain later, unless I forget, but which
many people consider as important, if not more important than turing
machines), we constructed turing machines by arranging and connecting the
states (we had a graphical tool for the task).  We had to do things like
write simple adders.  So, rather than say, take the number in byte 1 and
byte two, add them in byte 3, we took _111x1111_ (where the _s indicate
blank tape going off into space, also not the use of base 1, AKA
representing 3 and 4), and turned out _111x1111x1111111_. In otherwords,
since we can't address number 1 or number 2, we use marker bytes.  I don't
think that we even had to do multiplication (which I can't think of how to
do off my head, other than to hard "code" ever case).

OK, if I had some sort of general turing machine (as opposed to just an
adder turing machine) if front of me, in theory I could use marker bytes
to mark the parts of the tape, we could find the display buffer.  But, how
would we then get back to the part of the code we left off?

In theory, I suppose there is a way to work this out.  This problem
demonstrates some of the deficienies of the turing model.  It is just too
hard to use.  It can be greatly simplified by having a second tape, or a
few registers that states could increment or decrement, but that has it's
own complexities, and is generally reguarded as the deal killer.  Those
short cuts are really only good if you want to try to actually use a
turing machine for real work (as opposed to just using it as a
computational model).

This, finally, brings me to lambda calculus.  This has nothing to do with
derivitives or integrals, despite the name, I assure you.

Lambda calculus can be thought of as functional programming taken to the
logical extreme.  The basic idea is that everything is a function.  Ever
function takes one parameter (want more, just make you one parameter a
list), and evaluates one list(?) before returning? I'm not sure.  It is
like scheme, but stricter still.

For more on lambda calculus, see
http://www.csse.monash.edu.au/~lloyd/tildeFP/Lambda/Ch/ or
http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/

These days, CommonLisp is considered a functional programming language,
but there is enough build up that we can ignore that when it is
convienient.  Scheme, on the other hand, forces the issue.  Unfortunatly,
in the free market, Scheme is much more mature (more options, more
toolkits, etc), so I slog on, slowly, slowly, slowly.

--
Joshua Boyd

On Wed, 20 Jun 2001, Ken Hansen wrote:


> ** What do you call moving the tape? The tape is
> ** the memory, that was the inovation/value-add
> ** of the Turing machine model...
> 
> So, how would be know where how to find the display and packet buffers?
> 
> ** They indicate the state of the machine, why have buffers?
> 
> On a like note, in string lamda calculus, is there a solution to this
> problem?  Just represent the display as a really long list passed as part
> of a variable?
> 
> ** You've lost me - Calculus eluded me, that is
> ** one reason why I have a Humanities degree!
> 
> I know what lamda calculus is, but it wasn't covered at all in school, so
> I know very little about it.
> 
> ** You are one up on me!
> 
> --
> Joshua Boyd
> 
> On Wed, 20 Jun 2001, Ken Hansen wrote:
> 
> > The definition of a turing machine is that you have a box, and a tape running through it, infinitely long in either direction. The tape is one symbol "wide" (think movie negative).
> > 
> > The turing machine starts in an initial state. Then, based on the symbol/value of the frame of the tape inside the machien, it can either move to the left or right a discrete number of frames, and mark the current frame with a new value.
> > 
> > As the machine dances through these operations, it will be in different states, most likely related to the last symbol read from the tape.
> > 
> > Nothing I am aware of says the turing machine can or can not have a display indicating the current state of the machine (when you work through examples in school, you typically have a table that you fill in with the state of the machine at various points in the processing of the tape.).
> > 
> > That is about the sum total of my memory of turing machines, any more details will require me to pull out my Discrete Mathematics text from 15 years ago...
> > 
> > Now, the Turing test, is a whole different thing... ;^)
> > 
> > Ken
> > 
> > -----Original Message-----
> > From: Joshua D. Boyd [mailto:jdboyd at cs.millersville.edu]
> > Sent: Wednesday, June 20, 2001 3:58 PM
> > To: 'geeks at sunhelp.org'
> > Subject: RE: [geeks] Re: [rescue] RE: Absolutely nothing to do with
> > 'Small schools.& elections'
> > 
> > 
> > So, would the display be part of the tape, or is each display state a
> > machine state?  Would these just be a machine state for each pixel in the
> > display?
> > 
> > --
> > Joshua Boyd
> > 
> > On Wed, 20 Jun 2001, Ken Hansen wrote:
> > 
> > > Display? We couldn't even imagine a computer being able to display anything, we just "knew" what was going on in the game... Geez, anyone can play if you can just see the game in front of you... ;^)
> > > 
> > > Ken
> > > (Seriously though, I know of no reason why a turing machine couldn't have a display - it has a state, and it needs to communicate it to the user, so I would imagine in the strictest sense it would have to have a display, but the display may not be of a form familiar to today's "pampered" users, maybe a series of blue LEDs, or a scrolling LED array, like those found in grocery stores... ;^)
> > > 
> > > -----Original Message-----
> > > From: Joshua D. Boyd [mailto:jdboyd at cs.millersville.edu]
> > > Sent: Wednesday, June 20, 2001 3:18 PM
> > > To: 'geeks at sunhelp.org'
> > > Subject: RE: [geeks] Re: [rescue] RE: Absolutely nothing to do with
> > > 'Small schools.& elections'
> > > 
> > > 
> > > Is it really a turing machine if it can drive a display?
> > > 
> > > --
> > > Joshua Boyd
> > > 
> > > On Wed, 20 Jun 2001, Ken Hansen wrote:
> > > 
> > > > Ever tried to play Doom on a Turing machine? That was rough... (but it did run Linux!)
> > > 
> > > _______________________________________________
> > > GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks
> > > _______________________________________________
> > > GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks
> > > 
> > 
> > _______________________________________________
> > GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks
> > _______________________________________________
> > GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks
> > 
> 
> _______________________________________________
> GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks
> _______________________________________________
> GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks
>