see below, plz.
Dick
----- Original Message -----
From: "Tony Duell" <ard_at_p850ug1.demon.co.uk>
To: <classiccmp_at_classiccmp.org>
Sent: Friday, April 12, 2002 12:56 PM
Subject: Re: TTL computing
> > > I think that _any_ computer with finite memory (and that's all real
> > > computers) cna be shown to be equivalent to a state machine. Things like
> > > turing machines and PDAs [1] are only more powerful than state machines
> > > because they have infinite memory.
> > >
>
I must have slept through that class, since I've never been introduced to
anything physical that's infinite, and I've never seen a computer that's not
physical. I've seen machines that were virtual running on machines that are
physical, and that's what a microcoded machine is.
>
> > I've argued that in the context of exhaustive system testing. Any
computer,
> > and, in fact, the worldwide computer resources, viewed as a system is
still
> > bounded, though very large, and could, in theory, be viewed as a finite
state
> > machine. I challenge you, however, to come up with a way to validate such
a
>
> True...
>
> > system, whatever the size, using a computer, such that every possible
> > combination of bits in mass storage, in semiconductor memory, and in
inputs
> > and outputs, is exercised and the system behavior rigorously
characterized.
>
> Even exhaustively testing small (by today's standards) -capacity RAMs is
> likely to be impossibe. You can't cycle through the 2^65536 states of a
> 64K DRAM (Even at 1 state every us, it would take many times the age of
> the universe!)
>
The 64K DRAMs I had only had 2^16 bits, each of which had two states. My old
6502 would test his RAM, static though it was, but still 64K of it, in the
time it took me to consume a couple of beers, and I didn't get this gut from
sipping 'em.
>
> > >
> > > [1] Push-Down Automata. A state machine with an infinite stack linked up
> > > to it. Not any other expansion of that acronym.
> > >
> > How do you create an infinite stack? I'd submit that if it has an
infinite
> > anything, it isn't a Finite State Machine.
>
> True...
>
> As I understand it, (and this is not really my field), there are several
> theoretical constructions. These 'machines' are defined as accepting
> 'words' (strings of characters) from a 'language' (a set of said strings)
> and ending up in some internal state depending on which string we read.
>
> For example, a 'word' might be any string containing 'a's and 'b's only.
> The strings the machine will 'accept' are those consisting of an
> arbitrary number of 'a's followed by one 'b'. And we end up in one state
> if we have an even number of 'a's before the 'b', a different state if we
> have an odd number.
>
> This problem can be solved (IIRC) by a finite state machine, which (as
> used here) is a theoretical concept very similar to the electronic state
> machines we all know and love.
>
> But there are some problems an fsm can't solve. For example, consider
> strings of an arbitary sequence of a's and b's. At any time I want to
> know if the number of 'a's read is the same as the number of 'b's read.
> That can't be handled by an fsm because essentially we need to keep a
> count of 'a's. and this count could get arbitrarily large. There is no
> way of making an infinite counter in an fsm.
>
Yes, but that's because there's no way of making an infinite counter. As for
the business of counting, if you can have an infinitely long string of
characters and an infinitely deep stack, then you can have an infinitely long
counter, a state-machine in itself, and that can deal with your problem.
>
> So the fsm has been (theoretically) extended, by giving it infinite
> memory in a sense. One way is to add an infinite stack (using the normal
> definition of 'stack') onto which you can push characters and later pop
> them off and act on what was popped. The rest of the machine is still a
> fsm -- you've isolated the infinite part in the stack only.
>
Well, they don't build stacks that don't have counters in them, and those are
FSM's. Until you can come up with a physical stack that's infinitely deep,
this point is moot.
>
> This machine (called IIRC a PDA -- Push Down Automaton) can solve more
> problems than the fsm, but there are still some it can't solve.
>
The detail that's been omitted is that you can't build a physical stack
without a FSM, in the form of an up/down counter, since you otherwise haven't
any means for manipulating the stack pointer. You can't have a infinite stack
because you don't have an infinitely large memory, though some of the ones
they sell nowadays, and what you're going to have to have for the next release
of Windows, may seem that large. You can put terabytes of RAM in a box and
address it as though it were a mass storage device, or as though it were a
stack. It's up to you, but it's still finite, even if you have hundreds of
exabytes.
>
> Then there's the Turing machine. Again, an fsm with infinite memory (the
> 'tape), but memory that can be sequentially accessed one cell at a time.
> I believe nobody has ever proposed a machine that's more powerful than
> the turing machine. I also seem to remember that a PDA with _2_ separate
> infinite stacks is proveably equivalent to a Turing machine.
>
> OK, those of you who actually learnt some computer science, please correct
the above...
>
I see a major implementation problem, in that you throw around the word
infinite quite freely. It's possible to build counters of 2^64 bits, and it's
possible to hook up 64TB memory arrays, but it's still nowhere as large as
infinite. Until you have an infinitely fast computer, it wouldn't make sense
to have an infinite memory, since you wouldn't be able to test/verify
whether/that your infinite stacks, or whatever, work properly. If you can't
do that, it's not useable.
>
Received on Fri Apr 12 2002 - 18:55:08 BST