Re: Why the F21 is such a great idea! =)

[Nick Cabatoff <ncc@xxxxxxxxxxxx>]

Interesting... theoretical comp. sci. questions that even I know the
answers to, mostly.  This is a first.

On Jul 16, Alan Grimes wrote:
> 	I've been reeding some in one of my musty old books and I came
> 	across this. 
> 
> Finite state machines only handle Regular Grammars!

True enough, as with any finite automata.

> A stack machine. (Pushdown Automaton) allows the use of a "Context
> Free gramar" (whatever that is). 

A CFG is any language that can be recognized by pushdown automata (PDA),
which are nondeterminative finite automata with an infinite stack.
Because you can only access the stack from the top, there are processing
tasks that are beyond this construct (i.e., languages that it can't
recognize.)

> A Turing machine is the FSM given unlimited memory. 

No, a TM is kind of like a PDA that replaces the stack with a tape, i.e.
a randomly accessible memory (although since I've always seen PDAs
constructed using nondeterministic finite automata, it's probably better
to speak of a TM as a FSM with a tape, rather than a PDA whose stack has
been swapped for a tape.)

Typically the tape is infinite, but there are TM variations with finite
memory, which are in some respects more capable than a PDA with an
infinite stack.

> A Moore machine is an enhanced/ more efficient Turing machine that uses a
> pushdown automaton instead of a FSM as its controller.

No, a MISC chip is a TM like just about any other general purpose CPU.
It happens to be organized in such a way that stack operations are
convenient, but memory isn't accessed as a stack, and if it were the
chip would be handicapped.  It is no more or less capable in terms of
computing power (by which I mean tasks it can perform) than any other
CPU, it just happens to be more efficient in some regards.

> The question I am eggzamining today is: Is there anything beyond that?

Well, apparently Turing postulated a step above the TM, though I forget
the name he gave it.  It can solve problems that a TM can't.  You'll
love the design:  it consists of a TM and a black box (oracle).
Basically, the oracle provides the answers to any questions the TM can't
answer itself.  Of course, the contents of the black box is never
disclosed. :)  I must have missed the point somewhere along the line,
because this just reads like a joke rather than a theory to me...

> What is the next step? 

I'm not aware of any real progress made on having machines solve
problems that TMs can't (disclaimer: I'm not in, and never was in, the
loop.)  This is kind of the holy grail of theoretical computer science,
or rather it's one way of expressing it.  Nondeterministic TMs can solve
some problems in finite time that traditional (deterministic) machines
can't, but we're still a long ways away from that... though I admit that
whenever I fantasize about BIG networks of F21s, I always dream about
emulating a NTM.  Sooner or later though you run out of chips, and if
you can only go a handful of steps into a processing problem you don't
have a real NTM, or at least not a useful one.  [For the uninitiated, a
NTM splits itself in two whenever a branch could occur, and both branch
possibilities are explored by the two new NTMs.]

> The Celular Automata answer is to stack an unlimited number of
> Finite State Automata. 

I think you're confused on this point to, but I won't address it as I'm
not too familiar with cellular automata myself.

> Where ecah cell on turing's tape becomes its own machine.

This is a meaningless concept, at least as you articulate it here.