Computers Without Memory - Computerphile

They're called 'Finite State Automata" and occupy the centre of Chomsky's Hierarchy - Professor Brailsford explains the ultimate single purpose computer.

Note: Professor Brailsford omitted the transition from the 5 state to 25 state by means of a 20p, he has amended the linked notes!

Professor Brailsford's t-shirt kindly supplied by Peleg Bar Sapir

This video was filmed and edited by Sean Riley.

[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

[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

[Rob-wvqo]

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

[jorunessa]

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

[boblake]

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.

[AmeerFazal]

This man really know how to explain stuff :D

[xbaadfd]

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.

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

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

[RomanSoldier]

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

[_framedlife]

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

[WeeWeeJumbo]

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

[frankharr]

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

[asdddddaaaaaaaaa]

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

[massimilianotron]

Could you make a video about how people make programming languages, what kind of software is used to build them, etc?

[gnagyusa]

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

[jenniferw]

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

[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

[andredejager]

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.

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