Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel <oliver@first.in-berlin.de>]

Hello Bill,


On Sun, Feb 05, 2006 at 04:22:16PM -0600, Bill Wood wrote:
> This is a follow-up of my earlier (apologetic) post to you.  After
> reading your post stating that the C block was supposed to be an
> internal memory, I thought about how my model would have to be changed
> to get the right behavior of the C block.


Well, after I saw my fault of forgetting and then have re-read
HvF's papers, I started with the type (I learned that this
 really helps in design... this was (one of) my insight(s) for
 tonight... well, that is the reason why Simon J. Thompson
 in his Haskell book often started with the type-stuff...
 ...hey, this is the overall-structure, which helps in design
 more than simply writing down the idea of the algorithm!)
of the trivial machine and right after it with the
structure of the non-trivial machine.

With a block diagram and the attempt to start with the types
I got the following:
   (to mention: in the original HvF's graphic
    A is called F
    B is called Z
    C is called z
    u is called z'
    x is called x
    y is called y

       ... I can put it on the websrver also if someone is interested.)


   The I have created the following types:

   F (formerly A)  has type:      input_t -> state_t -> output_t
   Z (formerly B)  has type:      input_t -> state_t -> state_t
   z               has type:      state_t -> state_t


  Zjese are the ingreidents of the NTM,
  but looked from the outside (black box !!)
  it has the type:

     input_t -> output_t


I thought about what HvF meant, and then I got it:
When he speaks about the function F (formerly A)
this is the function that makes the calculation
form intput-value to output-value, but it's NOT ONE
trivial machine... the internal state switches between
some trivial machines, and the function that does
the switches is the Z (formerly B).

So, even if you have only simple/stupid machines
that are - in functional programming paradigm's language -
simple mappings between input and output - so this is
what we have as a function (or operator) in a functional language,
even if these stupid machines are underlying, the
NTM creates complexity by internally swiching between
some of these machines.

So, the internal state is used as a selector like in
a cicruit it would be a multiplexor: switch between
already existing functionality/channel/...

If you don't know how it behaves, you will have the problem
that you can't determine what's going on only from the
outside.

It was amazing to see the results of your machine!
It showed the complexity of this simple circuit much better
than only using integer values and do some operations on them.

When generalizing this machines (what I already had in mind,
but only now can think abouzt, since I used the attempt
with the general typing-stuff) it could be a lot of fun
to work with them and research on this, I think. :)


The next fine thing I then saw was: hey, to create the
NTM as a simple (from the outside, looking at the type)
mapping from
    input_t -> output_t
I have to use more input.... e.g. an array of TM's
(trivial machines),  which then internally (by the internal state)
will be selected as the mapping which will be active,
I saw: well, that's why the functional programing is so fine! :)

I can use arrays and functions and such stuff,
give it as arguments/parmeters to a function
and what do I get as a result?
A function. :)

Hey, again and again I see: this functional programming is
soo cool and such a wonderful thing... hey.... wow! :)

No pointer-horror... :)

I don't know if this mazing feeling one day will decay...
... for me it's always again amazing. maybe because
I started with Basic, then used C, then Perl, and now I'm here
in wonderland! :)


OK,
  it's better to stop now, if not... the size of this mail
  may get too big. ;-)


Sorry, not answering to all you wrote then, but well,
to late for today.... and I wan to code something,
before I go to bed. ;-)

Maybe more comments are following. :)

Ciao,
   Oliver