Simplifying Computers | Essence of Theoretical Computer Science #2

Previous video: https://www.youtube.com/watch?v=D7JBJ72R_I4&ab_channel=EasyTheory

Here we simplify our notion of a "computer". Most computers have many different inputs (e.g., keyboard, mouse, microphone, network, files) and many different outputs (e.g., speaker, screen, network request, file write). Here we simplify this notion without loss of generality by having exactly one input and one output by "multiplexing" the multiple inputs together. A computer then consists of three parts: (1) a single input string, (2) a single output string, and (3) a function taking those inputs and producing those outputs (sometimes we also read from an external storage medium, or allocate more of that, but those can be phrased somewhat as an input and output).

Of course, the "interesting" part is what happens in that function. Here we can phrase that as each instruction of the machine changing the "state" of the machine as a whole; without giving details (as this is theory), changing memory contents, storage contents, etc.

Additionally, we make a restriction on what the machine can do, which is essentially forcing the input to be read-only, and that we cannot acquire additional storage. This doesn't seem like a huge limitation, but it turns out that it is. The purpose of such a limitation is to make analysis and proofs of the underlying model really easy to do comparatively. Later in the series we will "unleash" the model once we have some proof strategies.

Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Dolev Abuhazira, Simone Glinz, Timmy Gy, Josh Hibschman, Patrik Keinonen, Travis Schnider, and Tao Su

Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs

Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com

▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=UZrv4gj2s3Y