Computers Without Memory - Computerphile

[@portaadonai]

That guy was born to teach. He loves it, he has a nice slow rhythm in speaking, and enunciates the words at just the right time

[@Triantalex]

false.

[@mikestoneadfjgs]

I love how in one video he said "if someone wants to make a shirt with this equation on it, i would wear it" and now he is wearing the shirt with the equation on it XD

[@noahwilliams8996]

+Charmonium Pentaquark I wish I had that shirt. :(

[@ais4185]

Supplied by Peleg Bar Sapir (see description), apparently

[@Triantalex]

ok?

[@boblake2340]

Finite state machines are everywhere, from stand-alone applications, like this vending machine example, down to the internals of processors and other complex logic chips. The only "memory" they need is a register holding the current state. And that "register" can be implemented with multiplexers (in which the next state is dependent on the mux's current state [outputs] combined with inputs from the system being controlled, and pre-programed input values, determined at design time ), or logic gates that compute the next state on the fly.

[@tscoffey1]

+Bob Lake But originally, in older vending machines, etc.- the "state" would just be the current configuration of all of the levers, toggles, et al, that have been changed due to the different types of coins being dropped in.

[@Triantalex]

??

[@Rob-wv8qo]

Am I the only one really annoyed that there isn't a 20p going from 5 to 25? >:(

[@aem5smruasn]

ikr

[@SK_Wizzard]

No your not ...

[@geryou8948]

+Robert Smith Ja, da fehlt ein 20er-Bogen von 5 zu 25.

[@FatherDraven]

+Robert Smith I had this same thought. :-|

[@Elbrasch]

+Robert Smith me too ^^

[@AmeerFazal]

This man really know how to explain stuff :D

[@LJdaentertainer]

+Ameer Fazal He's an ancient geek

[@0MVR_0]

He was at the battle of Troy long before SQL injection

[@donaldderp1602]

+Omar Omokhodion He collaborated with Archimedes, on building the first computer XD

[@tscoffey1]

+Omar Omokhodion Don't you mean "Greek Injection" (via the wooden horse)

[@Nozomu564]

+tscoffey1 Actually it's not an injection because it required installing a Trojan horse.

[@jorunessa]

7 years later this man, is still, improving students' lives, really thanks

[@Triantalex]

??

[@RomanSoldier13]

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

[@Triantalex]

false.

[@AvihooI]

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.

[@Triantalex]

??

[@imveryangryitsnotbutter]

It would be so simple to make a machine that handles overpaying. Just add 3 extra states: 30, 35, 40. - If 30, it dispenses a 5p coin if available, and moves to the 25 state. - If 35, it checks the weight of the 10p coins storage. Not empty? Dispense 10p and move to the 25 state. Empty? Dispense 5p if available and move to the 30 state. - If 40, it dispenses a 5p coin if available, and moves to the 35 state. This way, it refunds exact change if possible; otherwise, it refunds as much as it can without going over.

[@FortuneRayzor]

+I'm Very Angry It's Not Butter You're thinking too much about the actual implementation and that's not really the point here. You would just add those states to the diagram and named the transitions like -5, -10. The fact that the machine is unable to return 10p coin is irrelevant in this case.

[@3snoW_]

+I'm Very Angry It's Not Butter Simple and effective. Nice one!

[@TribeWars1]

Actually you don't even need the 25 state. You can make the output not only depend on the state but also on the input. If the state is 20 and you add 10p, just add logic that says 20 and 10p - - > print ticket, return 5p, state 0

[@sonotthere]

+TribeWars1 but it doesn't know the previous state. unless you mean it checks the state and value of the coin coming in.

[@imveryangryitsnotbutter]

***** I don't think the machine requires any memory to know what coins are available to dispense. Separating the coins does not require a computer; it can be done entirely mechanically. Vending machines have had such non-computerized systems for decades. The machine does not need to keep track of the exact number of coins in each chamber; it just needs to know whether each chamber is "empty" or "not empty". To that end, a non-computerized hanging scale is attached to each chamber. If the chamber is at its default weight (i.e. empty), then the levers within the scale complete a circuit which sends an electric signal indicating that the chamber is empty. However, if the chamber is any heavier than its default weight (i.e. it contains coins), the circuit is broken, and there is no electric signal.

[@asdddddaaaaaaaaa]

2 hours of parktime for 25p? Is this real?

[@rja421]

+Дмитрий Корьяс Maybe in 1970 lol.

[@lamkat2088]

+Дмитрий Корьяс Areas of Nottingham have 2 hours free for most(all?) car parks.

[@sugarfrosted2005]

+Дмитрий Корьяс The number was picked purely because it was small enough to not be long, but still enough to be complicated.

[@amreladawy3784]

+Дмитрий Корьяс We pay almost 38P for one hour only !!! And sometimes 58 for one hour.

[@EebstertheGreat]

+Amr ElAdawy Well around here parking meters might give you as much as an hour per quarter ($.25), but they don't print tickets (obviously; they're meters). You'll only get a ticket when paying to park in a lot or garage, which is much more expensive. Badly maintained parks on the fringes of the city might only charge $3/hr, but generally you're looking at $5-25 for the first hour. In Chicago and New York, it can easily be twice that.

[@rushilkonkata3622]

this is the knowledge I been waiting to learn im finally satisfied with this explanation thank you

[@jenniferw8963]

Thanks much for this video. I used a finite state machine when coding a library for sending SMTP mail back in 1994 -- it for an uncommon programming language. It sure made the coding very easy and you could visualize the code by looking at the graph. The graph was easy to draw because it made sense and the coding was like 15 minutes because I had the Finite State Machine. Thanks for refreshing my memory because I forgot how to even draw a finite state machine after not using htem for so many years :)

[@0xbaadf00d]

I remember getting onto an elevator, with people in it already. I pressed the button for my floor and the guy already in the elevator said that it's a grandpa-elevator. This left me with a puzzled look on my face. The guy continued, "no memory". Meaning that the elevator would not remember me pressing that button and I'd need to press it again when it next stopped. And this happened in Finland where nobody does smalltalk.

[@Triantalex]

ok?

[@andredejager3637]

Every time I watch this I understand more and more. Like 5,5,5,5,5 is one of the acceptable strings/words in the Language of the machine i.e will allow the transition to the end state.

[@sasukesarutobi3862]

Vending machines really have been around a long time: the first recorded one was built by Heron of Alexandria, who lived around 10-70 AD, and simply consisted of a machine with a coin slot that would dispense a fixed amount of holy water at a temple.

[@gnagyusa]

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

[@dariokartal9453]

You're not saying anything new. He never said that it isn't memory, but rather that devices with this ability don't need (to *have* ) memory (because they *are* memory). TO HAVE != TO BE. Memory doesn't need memory; it's already it. E.g. a simple computer code parser as he described doesn't need a variable to store the parser's state: the parser, just, *is* in some state. A coupla _while_ and _if then else_ arrows is all that such a parser needs to be in this or that state.

[@AureliusR]

@@dariokartal9453 That's... a bit of a stretch.

[@Triantalex]

??

[@m0hamedtajelsir]

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

[@snippletrap]

Memoryless is a technical term. It means that the next state only depends on the current state. See “memorylessness” on Wikipedia.

[@aleksandersuur9475]

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.

[@Wanttofanta]

I don't know what it is, but there's something i love between the way he describes things and his voice :D

[@Schindlabua]

Fun fact: In PHP your variable names can consist of only numbers. $1 = "Hello World"; // Syntax error: Unexpected '1' (T_LNUMBER) yada yada ${1} = "Hello World"; // works just fine Which is funky, since in the PHP docs it explicitly says "A valid variable name starts with a letter or underscore, followed by any number of letters, numbers, or underscores". It seems like that rule is only enforced by the parser and can be circumvented easily anyway! PHP is also a big mess though, so stuff like that is to be expected.

[@yyny0]

So technically you are not using a actual PHP interpreter/compiler/repl/whatever-it-is :D But I've heared people say GCC isn't a C compiler either.

[@yyny0]

So technically you are not using a actual PHP interpreter/compiler/repl/whatever-it-is :D But I've heard people say GCC isn't a C compiler either.

[@yyny0]

So technically you are not using a actual PHP interpreter/compiler/repl/whatever-it-is :D But I've heard people say GCC isn't a C compiler either.

[@feldinho]

+Schindlabua ${"💩"} works to. with that notation, the variables can be anything!

[@Schindlabua]

Felds Liscia Haha, that's amazingly awful. It looks like anything that PHP can coerce to any string works. ${""}, ${[3]}, ${new SplTempFileObject()}, knock yourself out! :D This language never fails to surprise me.

[@I_am_Allan]

What you spoke about, reminded me a LOT of the IBM PS/2 'terminals' I used in 1995(ish) at school. They had NO HDD's, and very very limited memory ... they were 'token ring' connected to "Enterprise" the schools mainframe. When I'd log in, I was logging into the mainframe, and the actual terminal was ... well like the "slim" terminals of today. My data was 'stored' (much like the cloud) on the mainframe server. IBM was ahead of the time with "slim terminals" and "cloud computing" I guess!!

[@noahwilliams8996]

+Allan C-B History sure does repeat itself doesn't it?

[@I_am_Allan]

Noah Williams Absolutely ! Though ... vending machines were around before IBM's PS/2 LoL

[@frankharr9466]

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

[@Triantalex]

??

[@marcduperron6062]

Finite State Automata = Regular Expressions The base for syntax parsing in programming languages. Alan Turing was a master in that field.

[@yuzan3607]

I don't know if you're still here (after 5 years), but can you explain exactly how syntax parsing is a finite state automata? I'm interested in that.

[@heraldo623]

​@@yuzan3607they mean a syntax parser can be modelled as a finite state machine. The state machine reads all characters from the syntax input in order. Each character triggers a state transition. If the machine reaches the final state, the syntax is valid, otherwise it's not.

[@WeeWeeJumbo]

Ay ay ay COMBINATORICS. I feel like this guy must be a terrific professor

[@Triantalex]

??

[@IceMetalPunk]

This brings me back to my Models of Computation course days at uni...and my Foundations of Computer Science course...and my Programming Language Design course...actually, guys, these things are everywhere in computer science XD

[@jakejakeboom]

embedded systems, hardware VHDL design... even in computer/electrical engineering

[@IceMetalPunk]

jakejakeboom Huh. I don't remember discussing FSAs in my embedded systems course...but that was only one semester years ago, so I could have just forgotten XD

[@BillySugger1965]

+IceMetalPunk in embedded control engineering we just call them state machines. Very simple to define complex behaviour which is fast to implement and easy to get right with predictable behaviour. Gives you a lot of performance with little risk of bugs. And starting with a state diagram like that shown means it's easy to get your head around the function and make changes when needed.

[@doid3r4s]

+IceMetalPunk If i remember correctly, the control unit of a MIPS multicycle is modeled as a state machine.

[@yuzan3607]

Are they useful for computer scientists? meaning did you use them in your job? It'd be ironic if you've never had to use them, and me an engineer who knows nothing about all of this am back to learning them because I need them in my job.

[@chrisofnottingham]

Just to point out that a state machine like that is itself memory. It knows what state it is in and maintains that state until it gets a new valid input.

[@RussellTeapot]

Thank you so much Professor Brailsford, I love this topic... And I have to admit, at least for me you Sir are the best at explaining something! The enthusiasm is intense, it's like a grandfather telling old stories near a campfire..I just love it.

[@zTheBigFishz]

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.

[@TymexComputing]

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

[@1st1anarkissed]

I really enjoyed that. I learned all of that new and some of it wasn't able to sink in, but most of it really tickled the neurons, so thank you!

[@RiscTerilia]

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

[@gothxx]

I would so much like to work with finite state machines and epsilon transitions, the graphs are just so beautiful.

[@dreamhollow]

I love this guy. I could listen to him for hours.

[@_framedlife]

I can listen to this man and Tom Scott all day and not get bored

[@Scott-J]

I always enjoy the videos with Professor Brailsford. This one is no exception. Thanks very much!

[@hamed9327]

great great explanation

[@kilésengati]

At the time this video was released we started the very same topic in the 12th class informatics course at my school.

[@silenthill8312]

Very well explained, thank you

[@snippletrap]

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.

[@RonJohn63]

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

[@nargisbanu523]

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

[@KarlFFF]

5:32 - I think that most machines, even in the early days, use the width of the coins. Think there is a couple of numberphile videos about this working towards solids of constant width.

[@Space_Parrot]

This man was all over the place with his explanations

[@HemmligtNavn]

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

[@AiOinc1]

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.

[@suave319]

I love videos with this guy. He's enthusiastic and explains well.

[@patricksile]

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

[@kamoroso94]

Perfect timing! I'm just learning about these in one of my classes.

[@sebastiannielsen]

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.

[@dakshays6375]

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 KZbin , but I love watching Computerphile videos.

[@pedronied]

This guy makes paying a machine sound like a jolly walk in the park during an adorable day.

[@Cra0Net]

Professor Brailsford you are the best!

[@nexusclarum8000]

Bringing back good memories of when I was in university.

[@pepperoach]

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

[@NoriMori1992]

Pedro Paletta It's never the wrong channel. :D

[@Triantalex]

??

[@aonoymousandy7467]

Great series, I have learned a lot watching these videos

[@TheStevenWhiting]

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.

[@xybersurfer]

i don't think it would have helped. literally implementing the diagram would produce incomprehensible code, that would require this diagram to understand

[@david.kizivat]

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

[@jmalmsten]

About introducing a 25p coin. I remember spending two weeks in London a couple of years ago and I just found the coin-system bewildering. 1p, 2p, 5p, 10p... pretty soon I had a wallet filled up with 20 different kinds of coins (that's what it felt like at least) that I had to scrutinize and tally up to buy a mars-bar when I'm in a shop with 5 people behind me. The result? "Bugger this! Keep the change". This is me coming from a country that at the time had 3 kinds of coins. 1, 5 and 10 SEK. We had "öre" too that was 1/100th of a SEK. But we got rid of them because of the inflation they were basically worthless anyway. And it practcally works without fail. So my advice is to not introduce more denominations. Instead, simplify... 10p, 50p and 1£... do you loose some pennies due to rounding up and down? Yes. But just think of all the time and space wasted in general fiddling about with coins that aren't' worth the metal its minted on. The US system is just barely better at this. But even their smallest cents are worthless. I'd be perfectly happy if the quarter was the smallest one... or we can all just stop this nonsense and do away with cash alltogether. ok. Rant done... Interesting video by the way. I really like this channel. :)

[@MojoLikesPie]

+jmalmsten It's really not that difficult to understand, but then I am a native, so I've been brought up with the coin values.

[@mandolinic]

There are plenty of good applications for a finite state machine - but seriously this money counter isn't one of them! However, he's completely right about the computer language lexer - I've hand programmed several of these and they're great fun.

[@natrixnatrix]

You should do something on lisps.

[@asmallbabby4205]

Pretty good dissertation on simplicity.

[@talathion369]

They made the T-Shirt! Is this the first video where that shows up? Behind on a few episodes...

[@Meep3692]

In Ottawa it's $2.00 for a half hour, but you had to park so far away it takes a half hour of walking to get where you wanted to go anyways.

[@hares295]

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

[@HenryMcGuinnessGuitar]

Wonderful, clear explanation

[@DaveScottAggie]

If I remember correctly, traffic light controllers are also finite state machines.

[@SpackoEntertainment]

Do they really say Pee instead of pence in UK?

[@fredderfbobbobbill]

25p for 2 hours parking? Pffft.

[@szymongorczynski7621]

On car parks owned by the roads department.

[@joseph10097]

+James Gould **Steals your KZbin profile picture**

[@Triantalex]

??

[@shingshongshamalama]

>implying vending machines have anything as cheap as 20p

[@fabioxperuggia]

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

[@karankondhia3963]

What a guy, makes we love computersience

[@shreyaskumar3091]

The language that is taken as an example has one missing transition which is (5,10)-->25

[@valhar2000]

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.

[@expansivegymnast1020]

Awesome video!

[@unvergebeneid]

Finite state machines are used all the time in programming. To, well, keep track of states. Not to mention regular expressions which I was a bit disappointed to learn this video didn't mention.

[@IceMetalPunk]

+Penny Lane /regular\w+expres{2}ions?\w+(?:is|are)\w+fun/i

[@Schindlabua]

+Penny Lane He did a video about the Chomsky Hierarchy a week ago or so, I reckon regexes are coming :P

[@unvergebeneid]

Schindlabua Quite possibly. He could have teased them though :)

[@HackingVision]

Love the T-shirt Prof its awsome :).

[@PantsStatusZero]

128 valid combos?

[@TheHereticAnthem20]

He found the T-shirt he was looking for!

[@marwanMSFsabry]

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

[@xybersurfer]

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

[@ijf03208rek]

when people say that their computer isn't confused, it isn't.

[@moosemoomintoog230]

Mechanical computers like vending machines and parking machines have a known state which is analogous to a register, just like the video says. But a register is technically memory.

[@qyahb3822]

I think there is mistake here, the vending machine has not temporary hosting, the coin dropa straight to the coin box. Thus register state is not applicable

[@TanjoGalbi]

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.

[@circuit10]

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

[@Glutnix]

So can we expect a video on Regular Expressions soon?

[@ZXGuesser]

Actually we did have 25 pence coins, but they were only issued as commemorative coins and have since been replaced with the £5 coin so it's understandable that car park ticket machines wouldn't accept them :)

[@Muzer0]

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

[@beri4138]

In the past?

[@andrewkocurek195]

I want to know who eats a -bar- of chewing gum lol.

[@tushexable]

a doubt, just trying to understand, we would still need memory to program the states right, like each state needs memory to know how to transition to a different state, and the transitions themselves would be volatile or temporary memory space which can even be constant, since all it needs to remember is the transition to increment the state, once the new state is reached, the current transition can be deleted or overwritten by new transition. if this is true, then the complexity of FSM specifically DFA should increase with the number of states to reach the final state, it will always be finite, but it is not constant and varies based on the problem, example if the parking ticket price is increased to 50p we would need more states to reach the final state. so we do need memory in the machine right, memory is required for one state to remember how to progress given a transition, and the point where memory is not required is that no state needs a history of how it has been reached, it still would need memory to know how to progress to the immediate next state so the machine should require memory. some of these might be very basic doubts, just want to learn and happy to be corrected :)

[@toekneema]

great communicator

[@FortuneRayzor]

Comment section should just accept that a state in a finite-state machine is not in fact a memory. The machine itself can't access any information about the state, it is just in a state in any given moment and can jump to another state if a particular condition is met. States are named (5, 10, 15, etc.) in the picture just for easier explanation. All of this is purely abstract and can't be mixed with electronics or mechanics. It's true that when you implement such abstract machine, you will probably use a some kind of memory, but that's completely irrelevant in the theory of finite-state machines.

[@CristiNeagu]

25p for 2 hours parking!? Where!?

[@IBITZEE]

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!

[@anirbanc88]

awesome !

[@FortuneRayzor]

@Stephen Kamenar No it does not. It's an abstract concept and the example used im the video is only for easier explanation. Imagine a tree that has two states: "standing up" and "chopped down", then the transition between those states is simply chopping down the tree and because you can't really undo the transition, the second state is final (something that is a requirement for valid finite-state machine). Baaam, you have an example of finite-state machine that does not imply a memory in any way imaginable.

[@enargins]

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.

[@Mjbeswick]

It's a register which stores a pointer to the current state, not memory as in RAM.

[@billebob]

Isn't knowing what state the machine is in a type of memory? Or is the definition of memory more restrictive than that?

[@MsJavaWolf]

I was wondering the same. I think he didn't mean memory as RAM, but mamory as in recollection how you reached the state.

[@npc4126]

Storing a state isn't memory? WTF?

[@MrCrashDavi]

+

[@odioaleman]

K9 most awesome dog ever.

[@karlkastor]

+Jaime Cernuda Affirmative!

[@AiOinc1]

+Alex Trusk so did the BBC

[@Triantalex]

false.