Planar Machines in Theory

preview_player
Показать описание
Here we consider "planar" machines in the undergraduate Theory of Computing class, and whether they are possible to be made, that is, a machine whose drawing does not have edge crossings. We prove that for regular languages, context-free languages, and Turing Machine languages, there is a corresponding "planar" machine. For example, every regular language has a planar NFA.

Timeline:
0:00 - Intro
1:38 - Planar NFAs
10:00 - Planar PDAs
13:24 - Planar Turing Machines

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

The views expressed in this video are not reflective of any of my current or former employers.
Рекомендации по теме
Комментарии
Автор

i finally remembered my youtube password

The reason this was uploaded again was that YT borked some of the video in processing the first time.

EasyTheory
Автор

I graduated CS major, but still love to watch this kind of videos. Great to see you again.

ybjeon
Автор

Everyday I am more and more fascinated with the beauty of Theory of CS

emilinochkin
Автор

For the TM you could have presented a specific universal TM that has no crossings 😊

AssemblyWizard