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.

Computers Without Memory – Computerphile
Tagged on:                                                     

100 thoughts on “Computers Without Memory – Computerphile

  • February 3, 2016 at 9:50 pm
    Permalink

    Interesting but flawed. A state machine implies memory, otherwise its state would always be the same, thus rather stateless.

    Reply
  • February 4, 2016 at 3:40 am
    Permalink

    2 hours' parking for 25p? I want to live where you live.

    Reply
  • February 4, 2016 at 7:09 pm
    Permalink

    This is actually a really great introduction to automata and formal languages, great examples.

    Reply
  • February 5, 2016 at 7:51 am
    Permalink

    Why can not the programming lang be considered as some kind of memory?, per example: there should be a part that says "if it starts with a letter then its a variable", the lang itself is holding that information. Don't know about vending/parking machines though since i guess they don't use a programming lang.

    Reply
  • February 5, 2016 at 5:12 pm
    Permalink

    this example is not correct. this machine needs memory to retain the state it is in. not much but needs memory

    Reply
  • February 5, 2016 at 8:59 pm
    Permalink

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

    Reply
  • February 6, 2016 at 2:55 pm
    Permalink

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

    Reply
  • February 6, 2016 at 4:26 pm
    Permalink

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

    Reply
  • February 7, 2016 at 1:45 am
    Permalink

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

    Reply
  • February 8, 2016 at 2:58 pm
    Permalink

    REAL LIVE COINS OMFG!!!!!

    Reply
  • February 10, 2016 at 11:45 pm
    Permalink

    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.

    Reply
  • February 11, 2016 at 11:48 am
    Permalink

    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…

    Reply
  • February 11, 2016 at 5:09 pm
    Permalink

    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 😀

    Reply
  • February 12, 2016 at 1:36 pm
    Permalink

    He found the T-shirt he was looking for!

    Reply
  • February 18, 2016 at 6:38 pm
    Permalink

    how about event system vs finate machine

    Reply
  • February 19, 2016 at 5:00 pm
    Permalink

    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.

    Reply
  • February 20, 2016 at 5:34 am
    Permalink

    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).

    Reply
  • February 21, 2016 at 8:00 pm
    Permalink

    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"…?

    Reply
  • March 4, 2016 at 2:16 pm
    Permalink

    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.

    Reply
  • March 5, 2016 at 3:18 am
    Permalink

    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.

    Reply
  • March 5, 2016 at 7:20 am
    Permalink

    purpose build elektronics.the computer without processor.

    Reply
  • March 8, 2016 at 1:11 am
    Permalink

    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?

    Reply
  • March 13, 2016 at 6:55 pm
    Permalink

    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.

    Reply
  • March 16, 2016 at 7:55 pm
    Permalink

    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.

    Reply
  • March 18, 2016 at 9:58 am
    Permalink

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

    Reply
  • March 20, 2016 at 3:05 pm
    Permalink

    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.

    Reply
  • March 30, 2016 at 5:24 pm
    Permalink

    8:16
    INT Shaun;

    INT?!

    Reply
  • March 30, 2016 at 11:28 pm
    Permalink

    This man was all over the place with his explanations

    Reply
  • April 2, 2016 at 4:56 pm
    Permalink

    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?

    Reply
  • April 27, 2016 at 6:30 pm
    Permalink

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

    Reply
  • April 28, 2016 at 4:07 pm
    Permalink

    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.

    Reply
  • May 2, 2016 at 1:21 am
    Permalink

    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?

    Reply
  • June 1, 2016 at 8:40 am
    Permalink

    Pretty good dissertation on simplicity.

    Reply
  • June 1, 2016 at 12:07 pm
    Permalink

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

    Computers are also finite state automata.

    Reply
  • June 1, 2016 at 2:14 pm
    Permalink

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

    Reply
  • June 2, 2016 at 7:49 pm
    Permalink

    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.

    Reply
  • June 15, 2016 at 9:59 am
    Permalink

    UK doesn't have a quarter equivalent? Boo.

    Reply
  • June 16, 2016 at 1:16 am
    Permalink

    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

    Reply
  • June 22, 2016 at 4:29 pm
    Permalink

    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…

    Reply
  • July 7, 2016 at 11:58 pm
    Permalink

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

    Reply
  • July 8, 2016 at 1:36 pm
    Permalink

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

    Reply
  • July 20, 2016 at 8:08 pm
    Permalink

    "and I got real life uk coins here"

    😂😂😂😂😂😂

    Reply
  • July 23, 2016 at 8:59 am
    Permalink

    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.

    Reply
  • August 1, 2016 at 7:43 am
    Permalink

    When you Poutine a coin :')

    Reply
  • August 2, 2016 at 11:52 pm
    Permalink

    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?

    Reply
  • August 19, 2016 at 5:51 pm
    Permalink

    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.

    Reply
  • August 22, 2016 at 4:02 am
    Permalink

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

    Reply
  • August 22, 2016 at 4:00 pm
    Permalink

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

    Reply
  • August 30, 2016 at 4:07 pm
    Permalink

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

    Reply
  • September 15, 2016 at 7:38 pm
    Permalink

    Bringing back good memories of when I was in university.

    Reply
  • September 18, 2016 at 11:01 am
    Permalink

    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

    Reply
  • October 12, 2016 at 6:04 am
    Permalink

    I wish parking was that cheap.

    Reply
  • October 19, 2016 at 3:41 pm
    Permalink

    >implying vending machines have anything as cheap as 20p

    Reply
  • October 28, 2016 at 8:39 pm
    Permalink

    "Real live UK coins"
    Exiting!

    Reply
  • November 13, 2016 at 4:23 pm
    Permalink

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

    Reply
  • January 6, 2017 at 7:08 pm
    Permalink

    Love the T-shirt Prof its awsome :).

    Reply
  • January 26, 2017 at 7:57 pm
    Permalink

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

    Reply
  • February 19, 2017 at 10:37 am
    Permalink

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

    Reply
  • February 21, 2017 at 4:05 pm
    Permalink

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

    Reply
  • February 21, 2017 at 7:27 pm
    Permalink

    stack the coins if you need memory.

    Reply
  • February 26, 2017 at 11:11 am
    Permalink

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

    Reply
  • March 5, 2017 at 11:07 pm
    Permalink

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

    Reply
  • March 12, 2017 at 3:49 pm
    Permalink

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

    Reply
  • March 15, 2017 at 10:45 pm
    Permalink

    Parking lot and windshield…?

    Reply
  • April 28, 2017 at 2:26 pm
    Permalink

    2 hours parking for 25p? Count me in!

    Reply
  • June 4, 2017 at 7:35 am
    Permalink

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

    Reply
  • June 23, 2017 at 7:59 pm
    Permalink

    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.

    Reply
  • July 10, 2017 at 2:07 pm
    Permalink

    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.

    Reply
  • August 4, 2017 at 8:58 pm
    Permalink

    man now I want a turing gum

    Reply
  • August 29, 2017 at 1:09 am
    Permalink

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

    Reply
  • September 7, 2017 at 2:44 am
    Permalink

    context-free vending machine

    Reply
  • September 12, 2017 at 6:58 am
    Permalink

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

    Reply
  • December 6, 2017 at 11:55 pm
    Permalink

    I don't know why this is so interesting

    Reply
  • December 31, 2017 at 10:58 am
    Permalink

    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.

    Reply
  • January 28, 2018 at 5:52 am
    Permalink

    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.

    Reply
  • March 24, 2018 at 12:38 pm
    Permalink

    more line £25 with the price of parking now

    Reply
  • April 4, 2018 at 5:13 pm
    Permalink

    This man has obviously never paid for parking in Nottingham

    Reply
  • April 16, 2018 at 6:03 pm
    Permalink

    They do have memory though, flipflops.

    Reply
  • June 9, 2018 at 11:29 pm
    Permalink

    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.

    Reply
  • August 3, 2018 at 2:30 am
    Permalink

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

    Reply
  • August 11, 2018 at 4:18 am
    Permalink

    A bar of chewing gum?

    Reply
  • August 14, 2018 at 11:49 am
    Permalink

    Storing a state isn't memory? WTF?

    Reply
  • August 30, 2018 at 1:16 am
    Permalink

    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

    Reply
  • September 3, 2018 at 12:23 am
    Permalink

    boilerplate guide. literally. lol.

    Reply
  • September 11, 2018 at 6:54 am
    Permalink

    Mmmmm….Automata

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

    Reply
  • September 19, 2018 at 1:50 pm
    Permalink

    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?

    Reply
  • October 29, 2018 at 4:48 am
    Permalink

    Great series, I have learned a lot watching these videos

    Reply
  • November 16, 2018 at 9:51 pm
    Permalink

    great communicator

    Reply
  • November 27, 2018 at 11:48 am
    Permalink

    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

    Reply
  • December 14, 2018 at 5:35 pm
    Permalink

    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.

    Reply
  • December 26, 2018 at 3:55 pm
    Permalink

    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.

    Reply
  • January 5, 2019 at 8:10 pm
    Permalink

    Forgot 5 + 20 on the diagram.

    Reply
  • January 11, 2019 at 4:00 pm
    Permalink

    wont it need memory to store the current number?

    Reply
  • January 29, 2019 at 9:34 pm
    Permalink

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

    Reply
  • May 29, 2019 at 1:22 pm
    Permalink

    so a pool table is also a computer without memory

    Reply
  • July 25, 2019 at 7:14 pm
    Permalink

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

    Reply
  • August 10, 2019 at 8:54 am
    Permalink

    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.

    Reply
  • August 21, 2019 at 4:08 pm
    Permalink

    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!

    Reply
  • September 19, 2019 at 5:36 pm
    Permalink

    Gripping

    Reply
  • October 8, 2019 at 3:49 pm
    Permalink

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

    Reply

Leave a Reply

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