Computers Without Memory – Computerphile


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.

100 comments on “Computers Without Memory – Computerphile”

  1. lnpilot says:

    Having the ability to store a state, is memory, whether that state is stored mechanically or electronically.

  2. Ali Al-Mahdi says:

    For all those who have more than 4GB of RAM you should be ashamed of yourself!

  3. Angry Face says:

    Is it strange that I love the feeling of watching these kinds of videos and feel totally confused?

  4. c muller says:

    Knowing the current state IS having memory. Little but not zero memory.

  5. Jesus says:

    REAL LIVE COINS OMFG!!!!!

  6. TymexComputing says:

    Yes, the missing transition from 5 to 25 is the one that caused me a headache but i'll just call it a feature 😀
    The speck in the eye of his neighbor see and log in ones not to notice.

  7. David Kizivat says:

    In my language we actually call vending machines "automat" as well as the state machines. When I was telling people that I have exam from automata they instantly assumed I attend a course that's all about vending machines…

  8. TheGreat Donkey says:

    So i guess that's the reason you write binary/hex 0b/0x in Java is so the Number starts with a Number and not a Letter 😀

  9. TheHereticAnthem20 says:

    He found the T-shirt he was looking for!

  10. CarouselBlind says:

    how about event system vs finate machine

  11. Weuyn says:

    I use the vending machine in the reception of my apartment building for converting my 5p coins into coins that I can use in the washing machines, heh.

  12. Hemmeligt Navn says:

    If I may add a little correction – in a typical DFA (Deterministic Finite Automaton) for a compiler's scanner module – the 'end of an identifier' is not limited to a ; or a , but more reasonably anything that is NOT allowed to be part of a variable name, so if a variable name consists of a starting letter and a any number of letters or digits (letter (letter | digit)* which read a letter followed by any number of (either a letter or a digit) ) [ this is called the equivalent Regular Expression] [ For each regular expression there exists a DFA and vice versa] then typically the 'end' is denoted by anything NOT a letter or a digit.
    so you would start in state 0 and to go to state 1 you need to see a letter, if you see anything else you go somewhere else (or error) in state 1 you keep recursing for as long as you see letters or digits and if you ever seen anything that is not a letter or a digit you go to state 2 and accept an identifier (without removing the last character you read as it will be needed in the next invocation of the machine).

  13. Szucs Istvan says:

    Depends on how you look it, those computers still have a memory, even if mechanical but they know how much money you put in. It does not know how did it get there or how much does it have totally but when the buyer begins putting in coins there is a temporary memory. Its really like a variable actually because a computer does not have to know anything other than numbers are adding up to it and at 25 (as an example) it will do something, then it will reset, regardless of what the result is.
    The other thing is, because you mentioned vending machines, either way you put it (mechanical or digital) the machine will get the message of what you want and will wait for the proper amount of money and will no what actions to perform so it can give away the following product. I'm probably complicating things but either way its still a form of memory whether or not it can be altered by the user or the device itself. The only thing with these is that this is rather a "mechanical approach"…?

  14. Lorenzo Benito says:

    I thought this was going to be about a computer I read about once (I can't remember where, or the computer's name) that had several hundred individual CPUs, each one connected to another 16 CPUs, and memory (other than, presumably, the registers in each CPU). The idea, apparently, was that the computer could, at any given time, hold all the information it needed to work with in the CPUs themselves, and had no need for system memory.

    I was curious to see if I would learn more about how that computer worked, and how successful the design was ultimately deemed to be.

  15. Sebastian Nielsen says:

    In most cases, the parking meters here in sweden, will never reject a overpay. If you overpay, theres 2 possibility things that can happen: Either, it will do as nothing happened, eg it will allow you to pay for as much time as you want. HOWEVER, if you pay for lets say 4 hours on a 2-hour max park, then the person who are checking the parking spaces, will check the "issue time" on the tickets (valid from), and if that is more than 2 hour ago, then you will get a fine for overstaying. The second case with parking meters is that they are programmed with the max-stay time, but then, if you overpay, it will then "swallow" any overpay and then issue a ticket exactly valid for the permitted period. So for example, if a max 2-hour park costs 25 SEK for 2 hours, and you put in 3 pieces of 10 SEK equaling 30 SEK, then it will accept 30 SEK payment and print a ticket valid only for 2 hour. The ticket will instead adjust the price, so on the ticket, it will not say "12,50 SEK per hour" instead it says "15 SEK per hour", so all the number on the ticket match up.

  16. Remy Brandt says:

    purpose build elektronics.the computer without processor.

  17. Bon Bon says:

    Since when Finite State Automata are considered computers? 😛
    Moreover, a FSM actually does have a memory! Its memory is the current state it is in at any particular moment of time, because the state is being remembered.
    I am not a professor, but somehow I know these things. So how is it that a professor doesn't seem to know it?

  18. AIO inc. says:

    Hey, if you're like me and like to write short programs in BATCH (which some could argue is not a programming language but I genuinely don't care), variables have to be surrounded by percent signs (%), meaning you can have any symbol or combination of symbols excluding the percent sign. This also means spaces, leading numbers, you can even name a number 999 should you want to, just by typing %999%.

    That's why I like using batch.

  19. Steven Whiting says:

    We had to make a program in our C++ class that acted like a vending machine. I clearly wasn't that good as it confused the hell out of me. I got help from asking online; once I got pointed in the right direction I finally understood what do to. That was back in 1999.

    I think this diagram would be helpful.

  20. Dan Kelly says:

    For further enlightenment search for "state diagrams". They have been used for decades.

  21. Jaye Bass says:

    No memory in principle but every State Machine implementation I've used (Harel State Machines usually) require lots of memory to handle transitions, guards, timers, the states themselves, entry/exit actions, etc. Qt, Rhapsody, QP, Sparx, etc. are all examples of useful state machines imps that require memory. This is the disconnect with the abstract field of CS and the people that actually do this stuff to make useful software.

  22. alexveldin says:

    8:16
    INT Shaun;

    INT?!

  23. Space Parrot says:

    This man was all over the place with his explanations

  24. Ray Kent says:

    for the simple example given here, the fsa approach seems more error-prone in design (he left a path out!) than just keeping a running total of value entered so far, which is childishly obvious. I can see the point for purely mechanical or similar implementation, but if we've got some silicon is there much point in this paradigm?

  25. RonJohn63 says:

    6:54 COBOL allows for variables starting with a digit. That was very handy before the language got more structured features.

  26. Harrian says:

    Am I the only one who finds it extremely frustrating he doesn't use the actual name of the concepts he's discussing?? How are viewers suppose to look into this more if they don't know that concepts he's talking about are Regular Expressions and Context Free Grammars.

  27. Jay Sheth says:

    he said that it is the memoryless machine, then how did it perform an addition 15(5+5+5 or 10+5). Can addition be performed in a memorylesss machine?

  28. A Small Babby says:

    Pretty good dissertation on simplicity.

  29. Mateusz Grotek says:

    Finite automata have memory. It's finite. The memory contains the current state.

    Computers are also finite state automata.

  30. Marwan Sabry says:

    Hats off for actually getting log2(10) = 3.322 on a t-shirt lol

  31. AvihooI says:

    The very first component in a compiler is a lexical analyzer which is perhaps a fancy name for an implementation of a finite state automata. It receives a stream of characters (probably encoded in some form to save space and computation time for reasons I cannot immediately explain) and just by moving from one state to another it knows to detect the appropriate token. It also associates a token with a lexeme which is the value of a detected portion of the stream of characters (for example, if the token is a number, then its lexeme might be the value of the number). Those tokens are then parsed by a syntactic analyzer (or parser).

    The power in lexical analyzers as said in the video is that they don't use any extra memory and they go over their input exactly once (that is to say, the memory complexity of lexical analyzers is O(1) and the time complexity is O(n)). The way they can be implemented is as simple as a two dimensional array that with the indices of it being the characters themselves and a special flag for each input receiving state (unlike conventional FSAs, lexical analyzers can have more than a single type of input receiving state – each type of state corresponding to each type of token).

    I personally find the simplicity behind them and generally compiler front ends to be incredible. Compilers are made of components, each extremely efficient and incredibly simple for the job it is doing. Yet together they perform a very important and complex task.

  32. lisamariefan says:

    UK doesn't have a quarter equivalent? Boo.

  33. M.T. M.E says:

    I didn't like the statement that the finite automata is a memory less system. I argue that the retention ability of the system to store the present state is itself a demonstration for the system to have a memory

  34. Mendieta says:

    The state machine is wrong, you should make states which will result in the machine giving change… For example you can give 3 "10p" coins and en up with 30p and the machine in this state will give you 5 p change and go to finish state.

    This is really basic…

  35. Matt Jackson says:

    Where is this parking machine? I was out with a friend the other day, two hours cost £3.50! 😐

  36. aullik says:

    2 hours parking is 4€ to 5€ where i live 🙁

  37. Koploper77 says:

    "and I got real life uk coins here"

    😂😂😂😂😂😂

  38. Fwind V says:

    This video is a bit misleading imo, the flip flops you would use to build that state machine are the same types that RAM uses, is RAM not considered memory?

    There are 2 types of memory that should be talked about here:
    – persistent memory
    – immediate memory

    It's true that this state machine has no persistent memory, but it does have immediate memory. It has to know what state it is in before stepping to the next state based on it's current state.

    So this video should be called Computers Without Persistent Memory.

  39. MK73DS says:

    When you Poutine a coin :')

  40. n00b_asaurus says:

    So can you guy's make a video translating a finite state diagram into a circuit? can you also explain how this is used in a push-down automata? and if you're really feeling like a challenge, explain how all that is used in a turing machine?

  41. aleksander suur says:

    The great way about finite state machines, or about writing an arbitrary program as a finite state machine, is that if you have defined all the possible states and all the possible transitions the program can never find itself in an unexpected situation. Highly reliable programs can be made by thinking of the processes as finite state machines. The example is simplistic, but any program can be converted to a fsm. You can have any number of states, inputs, outputs, transitions and if you loop an output to input you can call it a variable.

  42. Frank Harr says:

    Live British coins! SO much more exciting that the caught and stuffed variety.

  43. Heath Mitchell says:

    To deal with overpayment, when there is an illegal coin if it isn't 1p or 2p you could just print.

  44. Nargis Banu says:

    Only 2 days back I wrote that data structure mumbo jumbo for exam without understanding it's practical application. Now I get it! 😐

  45. Nexus Clarum says:

    Bringing back good memories of when I was in university.

  46. BenRangel says:

    But identifiying var names is not that simple. Even if it started with a letter and ended with a semicolon you still have to check that it wasn't a reserved keyword like 'int'. And in most languages you have to check that the name isn't already defined in the current context

  47. John says:

    I wish parking was that cheap.

  48. shingshongshamalama says:

    >implying vending machines have anything as cheap as 20p

  49. Cam Brown says:

    "Real live UK coins"
    Exiting!

  50. Picobyte says:

    Traffic lights,washing machines and jukeboxes do the same sort of stuff.But all have some form of mechanical memory.

  51. Hacking Vision says:

    Love the T-shirt Prof its awsome :).

  52. Ebonmourn says:

    His voice reminds me of Winnie-the-Pooh with a slight British undertone

  53. xybersurfer says:

    he talks about a computer without memory but presents a machine with state

  54. John Rickard says:

    Don't a lot of older elevator controllers work this way?

  55. FounderOf ISIS says:

    stack the coins if you need memory.

  56. RiscTerilia says:

    Modular synthesisers might be an interesting topic for a future computerphile video since they're actually special purpose analogue computers.

  57. Pedro Paletta says:

    If a parking machine can't handle overpaying, would you call it a parker machine? Oh, wait, wrong channel.

  58. Flankymanga says:

    Isnt the state itself a memory? Because the machine has to be in a state, it has to remember its state….

  59. James Petts says:

    Parking lot and windshield…?

  60. Matt Brewerton says:

    2 hours parking for 25p? Count me in!

  61. fede says:

    69 people program in Forth, Factor or some other language where identifiers can start with a number or symbol.
    1+ though 😉

  62. Galbi 3000 says:

    Surely the display of the amount entered so far is memory of sorts? It would be temporary memory that once the transaction is complete (I.E. the ticket printed) it gets cleared ready for the next coin to be inserted by the next customer. In programming terms it would be like a temporary variable in a function that is only used while that function is running.

  63. Falconpunch82 says:

    2:45 is wrong. Languages, natural or formal, are not finite-state machines, due to syntactic dependencies (Chomsky 1957). In other words, syntax requires memory, in that the obligatory presence of an item in a string necessitates knowledge beyond the current state.

  64. ivan pineda says:

    man now I want a turing gum

  65. Patrick Sile says:

    I love when this Sir speaks he breaks it down to the lowest level…

  66. mike johnston Bob says:

    context-free vending machine

  67. Aditya Choudhary says:

    https://youtu.be/thrx3SBEpL8?t=3m14s watch this and then look at his t shirt in this video. He is true to his words

  68. Veronica Star says:

    I don't know why this is so interesting

  69. nrgins says:

    He says the vending machine has no memory and doesn't need any, but that's not true. It has memory and uses it to keep track of what the total amount paid is. So it's one piece of memory that only stores the total amount paid thus far, but it's still memory.

  70. cryptnotic says:

    Any actual computer with finite memory is a finite state machine. If we live in a finite universe, then all actual computers that will ever exist will be finite state machines.

  71. highlandrab19 says:

    more line £25 with the price of parking now

  72. Matt Parkin says:

    This man has obviously never paid for parking in Nottingham

  73. F3udF1st says:

    They do have memory though, flipflops.

  74. superspit says:

    Unfortunately, it's the accountants and Sales Force that want to know everything coming into a food/drink vending machine (coin float/stock) and all that comes out of it (ie.stock and change given). Lately I only work on vending machines that have more memory than some of my early windows computers. Oh, and they're all GSM equipped too! Those mechanical and 'brainless' vending machines are only used by very small owner operators who don't mind manual stuff as they only have few machines in market. We (my company) have thousands.

  75. SevenDeMagnus says:

    Hi. Where does it store the current sum? Register is a short term memory?

  76. Will Suttie says:

    A bar of chewing gum?

  77. NPC says:

    Storing a state isn't memory? WTF?

  78. Atari Master says:

    Altair 8800 would have sepperate op codes for getting variable from memory or an actual number because variables were divine by memory location witch is also a number

  79. Victor Zed Wings says:

    boilerplate guide. literally. lol.

  80. Asura says:

    Mmmmm….Automata

    I friggin love that word, no joke
    It will never not be cool

  81. Matthew Grimshaw says:

    You claimed that this machine has no memory, but that it does remember the "state" it's in. But we could read the entirety of a Turing tape as a number, and call that number a state, claiming then by your argument that the Turing machine has no memory, but only "state". This machine has a finite number of states, which strictly speaking excludes the infinite-tape Turing machine, but any physical (and thus finite) realization falls back into this mess. It sounds like there's no difference between a zero-memory machine with state and a finite-memory machine. Am I missing something?

  82. Aonoymous Andy says:

    Great series, I have learned a lot watching these videos

  83. Tony Ma says:

    great communicator

  84. Duke of Markus says:

    Sadly there is a missing transition on the DFA diagraom. You can put a 5p coin, then a 20p coin, which is 25p. So there should be a 20p transition from state 5p to state 25p

  85. snippletrap says:

    The application to practical computer science is not checking variable names specifically. It’s REGULAR EXPRESSIONS in general. Every regular expression corresponds to a deterministic finite automoton.

  86. Rennie Allen says:

    Everything in computing is ultimately a FSA, the processor itself is a FSA. This video is misleading as it implies that FSA are some obscure corner case rather than what they are, which is the fundamental concept from which all digital computers are built.

  87. Dremák Gergely says:

    Forgot 5 + 20 on the diagram.

  88. Mr Happy Face says:

    wont it need memory to store the current number?

  89. OrcButter says:

    25p for 2 hours?! Not these days man lol

  90. Kevin Oduor says:

    so a pool table is also a computer without memory

  91. Jay Sistar says:

    I haven't seen a Computerphile video on pushdown automata. Do you take requests?

  92. mediocre man says:

    This video just gave me the idea to name my variables to start with an underscore and the rest be only digits. People who might read my code will hate me for that 😉 And rightfully so, if I really ever should do it. Hm, I have to give that some further thought I guess.

  93. ZEE IBIT says:

    I don not quite agree…

    You will need more than 1 register…
    You need one register for the accumulator (sum of previous coins, the finite state)
    and also one register for the current coin being analyzed to be accepted/rejected…

    liked the video, thanks!

  94. Trevor Reed Studios says:

    Gripping

  95. अंशुमान अवस्थी says:

    How do machines"recognize" the value of each coin?

  96. Dakshay S says:

    Can I hope for a video on Banker's algorithm for deadlock avoidance while resource allocation by operating system. I know there are lot of videos on this here in YouTube , but I love watching Computerphile videos.

  97. Steven Barnes says:

    2 hours parking for 25p lol. I just paid £17 for 7 hours parking in a UK hospital. If only you could get 2 hours parking for 25p

  98. Steven Barnes says:

    The diagram is missing the 5p and then 20p combination.

  99. feyzullah Bayın says:

    Türkçe altyazısı yokmuydu bunun

  100. Hashirama Senju says:

    25p for parking? in which world does he live in?

Leave a Reply

Your email address will not be published. Required fields are marked *