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 7:22 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
>
> Have you really never come across the theoretical 'machines' used to
> discuss what is 'computable' or not?
>
> This stuff is pretty useless _to me_ (I am not saying it's useless to
> everyone, so no flames) because, yes I work in the real world where
> machines have finite memory. On the other hand, I do find it interesting.
>
> > > 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
>
> True, which means there are a total of 2^(2^16) = 2^65536 = a darn big
> number [1] total states. I am not just talking about setting and
> resetting each bit in the word, I am talking about cycling the RAM
> through all the possible states. You did mention exhaustive testing...
>
> After all it's possible (albeit unlikely) that some particular
> combination of bits in locations 0, 3, 15, 3f, 2001, etc will affect the
> bit in locaiton 102c :-)
>
In a single device that would be true, but the upper limit on what you have to
do in order to effect an exhaustive test of the memory array is to test out to
the boundaries of each device, since that's what you can't examine with your
'scope. Beyond that, it's just the same logic regardless of the contents and
won't be impacted by what happens inside the devices, power phenomena aside,
of course. Those, again, are externally observable, however, so you needn't
walk bits from one chip to the next.
>
> > 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.
>
> Yes, but you didn't do an exhaustive test. Most likely you just did a
> 'write all 1's, write all 0's, write both patterns of alternating 1's
> and 0's, and then write bit patterns to make sure no address lines are
> shorted or open'. That's what most people do for a RAM test because it's
> the only way to do it in a sensible time. Exhaustive testing of all RAM
> states is impossible.
>
Not exactly. (see above paragraph) I was using 4Kx1-bit static memories back
then, so I had to cycle through 16 banks of 4K bytes, with every combination
of bits in each 4K-bit chip, but no further than that because any effects
exceeding the chip boundaries would be externally observable.
>
> > > 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
>
> Forget about real computers for the momnet
>
Why? This quagmire was originally entered over the question of what
distinction there was between what was referred to as a microcoded machine
versus a state machine. My position is that the terms and their usage had
specific origins due to the way they evolved and they found their usage on
that basis. Your position is that how these terms came to be used as they are
is not relevant, since the people who use them seem to differ in their outlook
from you. I don't believe your view is irrelevant, nor is it wrong. It's
just not aligned with what I seem to understand as the conventional usage.
You are intent on going on about what a state machine IS. I'm simply going on
about what most folks in the biz seem to understand a state machine to be.
Likewise a microcoded CPU. I don't deny that what these items ARE, and what
folks understand you to be talking about when you use those terms may in fact
be inconsistent with definitions from computer science or from electronics
engineering. I'm just cautioning you that your inferences from the domain of
raw math and theoretical comp sci don't exactly align with common usage. If
it's about being right, then you certain are. It's just that extrapolating on
the putative intersection of the theoretical definitions on one hand and the
paractically evolved nomenclature on the other isn't getting us anywhere.
What the terms SHOULD mean just doesn't happen, in your quite valid view, to
align with what common usage seems to indicate they DO mean to a large number
of their users.
I told it was a semantic quagmire.
>
> The whole point is that a finite state machine has a finite number of
> states. And thus can't be used to make a infinite counter. Now some
> problems on unbounded-size data streams can be solved without arbitrarily
> large counters (the first problem I mentioned, deciding if the number of
> 'a's was odd or even can, no matter how long the data stream is). Others
> cannot.
>
> Now, you could just say that, OK, we'll allow machines with effectively
> infinite numbers of states with as complex a transition diagram as you
> like between them. Problem is, it's hard to do any kind of meaningful
> reasoning with such 'machines'. Instead, lets keep the 'infinite' part to
> one particular section of the machine (the stack on a PDA, the tape on a
> Turing machine) and keep the rest as a finite state machine that we
> already know how to understand. And it turns out that 'machines' like
> this (Especially the Turing machine or the 2-stack PDA) can essentially
> do anything an 'infinite state machine' could do.
>
> > Well, they don't build stacks that don't have counters in them, and those
are
>
> Of course you can build a stack without a counter. In the real world a
> shift register will do it (I've used a row of 'F194s to make a subroutine
> stack). Or a pile of bits of paper with numbers written on them :-). You
> do not have to make a stack (particulary not in the 'theoretical world')
> using a counter
>
Oh forgive me for trying to be practical. It takes a LOT of shift registers
to build what you can build with an up/down counter and a RAM.
>
> > FSM's. Until you can come up with a physical stack that's infinitely
deep,
> > this point is moot.
>
> Again, have you really never come across these theoretical 'machines'
>
I've never had to sit in front of one and use it to do useful work.
>
> > 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
>
> Again, I claim you can. The idea of a stack pointer addressing normal RAM
> is a convenient way to make a stack using commonly available components
> in the real world, It is not the only way to make a stack, even in the
> real world.
>
You keep skipping over the practical details. Even the old DEC machines don't
build their stacks with discrete shift registers, unless they're very shallow,
indeed. I suppose an 8-level stack would work OK.
>
> > because you don't have an infinitely large memory, though some of the ones
>
> I thought we were all agreed that all real computers are FSMs, albeit
> with a ridiculously large number of states.
>
> > I see a major implementation problem, in that you throw around the word
>
> Agreed. Nobody is ever going to make (or even simulate) either a PDA or a
> Turing machine. Simply because real memory is finite.
>
So, outside the world of theory, they don't exist, hence, unless we're trying
to be theoretical, which I think we're not, discussion of these items as a
basis for nomenclature applicable to commonly used constructs will likely lead
nowhere.
While it's true that a modern computer can be viewed as a collection of state
machines, or, in some cases, a single state machine, that's not what most
people think of when you refer to a state machine. Further, when you refer to
the notion of a microcoded CPU, people generally don't think of the ROM in an
old early '70's-style state machine as the microcode. Generally, I'd say they
refer to the sort of thing extensively discussed in the November 1984 issue of
Electronic Design, which has a number of articles on microprogrammed systems.
The main thing that characterizes them, in my own view, is that they have two
levels of code. The microcode firmware makes the computer compute in the way
in which it does, and the application or macrocode makes it do useful work.
That's an oversimplification, for sure, but since the two levels of code are
quite isolated from one another, it holds true.
Received on Sat Apr 13 2002 - 01:08:41 BST