For years and years, there have been, as part of our civilisation
special purpose electromechanical computers
and a classic example of these is vending machines.
If you put in the right combination of money, they will vend you a bar of chewing gum, or whatever.
And they've been around for so long that they really are largely mechanical.
They're a bit more sophisticated now because they've got microchips inside them
but they don't really need that.
We're going to look at the fundamentals of vending machines,
Or, if you like, very similar, how do I pay my car park charge
and get a ticket that I put on my windshield to say "Yes, I have paid".
What's the process of saying "you must pay me 25p" (if you're in the UK)
in the States, you must pay me 25 cents.
And I've got real live UK coins here.
This is one of the simplest finite state automaton examples that I know of
because I think you'll all find it familiar.
Here in the UK, if we're told that we have to pay 25p
typically you would have to choose from a five pence coin, a ten pence coin and a twenty pence coin
Unlike the USA, we do not have a 25 pence coin.
You cannot just, as it were, put one coin in
and that's 25 and you're done.
You've got to build it up out of any possible combination of these.
And if you look at this diagram with me, it's so simple.
It's just self explanatory.
You start over here, the machine has got no money in it.
You put in one of these 5p coins, and it goes "chunk!"
and it moves into what I shall call "the five state".
It's basically saying to itself "I'm happy, I've got 5p so far."
But it's not enough yet. Well, all right
Let's be a little controversial, let's make our second coin be a 10p coin.
Now we take this transition out of the five state
we've put in a ten coin
and it jet-propels us into the fifteen state.
So the machine, if only it had a brain, is effectively smiling and saying
"I'm on the way, I've got 15p"
but the aim is 25.
Well, there's two ways to get from 15 to 25, look
You either put two more fives in, that gets you there, or one ten.
And when you get to 25, I've put it inside a double circle
which is the convention, because that's the finish state, you've put in 25p.
And eventually it goes "bzzt, bzzt" and prints you out a ticket.
And because you've paid 25p, it entitles you to two hours of parking, or whatever.
All that this is doing is encoding in this diagram all the possible ways that you can build up 25p.
And if you thing about it, in a weird way, it's kind of like a language.
And the sentences in the language are possible ways to make up 25p.
So here's a legal sentence - this is the other way to think about it.
A legal sentence in this language is "five five five five five".
Another legal sentence, just using the words "twenty" and "ten" and "five" is
"twenty, five". That's a legal sentence: it makes up 25p.
How about "ten ten five"?
Ah! but then it could be in any combination
There's "ten ten five", "five ten ten", "ten five ten".
"five five five ten" works.
So you can go through this if you want to work out all of the many, many combinations that will get you to 25p.
It leaves you of course with situations like what happens if you overpay
you've only got three of these 10p coins, 30p.
Many say "if you overpay, I don't mind, it's more profit for me" and, you know, I'll give you the ticket anyway
Some, badly designed ones, just seize up and sulk.
But then if they seize up and sulk, the question is
in the end, is there a sort of reject button you can press
which says "I've given you too much, now give it all back to me" ?
Or does it just gobble it up and say "I'm sorry, it's an illegal amount, it's too much and I won't print your ticket"
and this gets people really, really annoyed when this happens.
But you all know the symptoms of exactly this sort of thing.
And like I'm saying, these are so commonplace, they've been with us for ages.
But the crucial thing I want to emphasise is the following:
If you're sitting there in the fifteen state
all that this machine says, or knows inside itself, if you like
is "I am in the fifteen state".
If you say to it "but how did you get there?", it would say "I don't know"
"I just don't know, I retain no memory of the coins I've had, to get me to this state at all.
I just know I'm in fifteen, it could have been ten and five, it could have been five five five.
Who cares? I'm in a fifteen state."
So that is why these are machines with no need for memory.
They are, if you like, a processing system that accepts coins.
And you could perhaps argue that it's the ultimate special purpose computer.
It's a special purpose dumb computer that vends tickets for a parking lot.
The only thing it does need is, when you put in a coin, every single coin, it needs a holding position.
You could think of this as being like a sort of register inside a central processing unit.
It holds the current coin and often will examine it.
And of course, in the early days, all it could do to check that it was valid was maybe weigh it.
Nowadays you can shine lasers at them, do spectroscopic analysis and all sorts to determine.
So the current coin is held in - I will always think of it as a sort of register, to hold it until it's decided to accept it.
And when it's accepted, it drops into a pot of all the coins you've given so far
and maybe when we're in the fifteen state we get another five, we go into twenty
but that latest five just goes "chunk!" and you hear it drop inside, and it's in the pot.
But the pot is amorphous, the pot has no knowledge of how those coins got in there and in what order.
It doesn't need to know that.
>> Sean: We've talked about vending machines, we've talked about parking machines
Is there anything that they get used for in computer science, maybe that's more of a kind of, technical...
>> DFB: Yes, vending machines, parking machines, the simplest thing, and what you're asking is:
"What's the thing that really turns on computer scientists that's that simple?"
I'll tell you Sean, what's that simple.
It's the rules for "What is a valid variable name in a language".
Now, if you've done any programming, you will know that the rule typically is:
A variable name - an identifier as they're sometimes called -
can be any combination of letters or digits, in any order,
but it must start with a letter, yeah?
So you can have "Sean", "Dave", they'll be variables, you can say they're integers, or whatever.
You can even have "k9" as a thing, but you can't have "9k", yeah?
Because anything beginning with a digit could be the start of a number.
And what languages do not want is to spend ages deciding whether "9999" really is meant to be a number
or, in some weird way, you're trying to name a variable.
Oh no, if it starts with a digit, it's gonna be a number isn't it?
If it starts with a letter, it's an identifier or a variable name.
And you can see with that, you could draw one of these diagrams.
You could say, come in, is it a letter? Fine.
Next state. Is it a letter? Fine. Go back, recursively into yourself and expect more letters.
Or, is it a number? Loop back recursively into yourself again.
You've got a loop coming out and back in again with "letter" on top of it,
and a loop at the bottom, saying "digit" on the bottom of it.
And you can keep going round and round, taking any combinations of letters or digits
Until typically what happens is you come to a sort of "end symbol".
And in a program, what will happen of course, is that you'll have a semicolon.
int sean;
That says, that's the end of the identifier.
Or sometimes it'll be a comma, if you're declaring lots of things.
But there's always some end symbol that tells you "end of identifier".
And you say, is that legal?
You don't need anything fancy to recognise that that's a legal identifier!
you don't need stacks, you don't need tons of RAM, it's just one of these things.